<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1,user-scalable=no"><title>数据结构和算法 | 麻辣兔头川菜馆</title><meta name="keywords" content="学习笔记,数据结构,算法"><meta name="author" content="寒兔丶"><meta name="copyright" content="寒兔丶"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="常用数据结构数据结构 考研 找工作 记忆性、理解性 代码实现 证明理解了的最高表现形式 代码实现对记忆、理解 促进作用 实现要比记忆、理解难得多 记忆、理解  数组（动态化） 栈    递归   斐波那契数列 链表    增删方便  查找费时    适用于频繁增加或者删除的场景 图      邻接矩阵    邻接表 散列表    哈希冲突 队列    多线程阻塞 树        平衡二叉树、红黑"><meta property="og:type" content="article"><meta property="og:title" content="数据结构和算法"><meta property="og:url" content="https://mengfanmingx.gitee.io/posts/2022/12/24/data%20structure&algorithm/"><meta property="og:site_name" content="麻辣兔头川菜馆"><meta property="og:description" content="常用数据结构数据结构 考研 找工作 记忆性、理解性 代码实现 证明理解了的最高表现形式 代码实现对记忆、理解 促进作用 实现要比记忆、理解难得多 记忆、理解  数组（动态化） 栈    递归   斐波那契数列 链表    增删方便  查找费时    适用于频繁增加或者删除的场景 图      邻接矩阵    邻接表 散列表    哈希冲突 队列    多线程阻塞 树        平衡二叉树、红黑"><meta property="og:locale" content="zh_CN"><meta property="og:image" content="https://mengfanmingx.gitee.io/img/default_cover1.png"><meta property="article:published_time" content="2022-12-24T09:25:45.738Z"><meta property="article:modified_time" content="2022-12-24T09:50:05.254Z"><meta property="article:author" content="寒兔丶"><meta property="article:tag" content="学习笔记"><meta property="article:tag" content="数据结构"><meta property="article:tag" content="算法"><meta name="twitter:card" content="summary"><meta name="twitter:image" content="https://mengfanmingx.gitee.io/img/default_cover1.png"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="https://mengfanmingx.gitee.io/posts/2022/12/24/data%20structure&amp;algorithm/"><link rel="preconnect" href="//cdn.jsdelivr.net"><link rel="preconnect" href="//busuanzi.ibruce.info"><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.min.css" media="print" onload='this.media="all"'><script>const GLOBAL_CONFIG={root:"/",algolia:void 0,localSearch:{path:"/search.xml",preload:!1,languages:{hits_empty:"找不到您查询的内容：${query}"}},translate:{defaultEncoding:2,translateDelay:0,msgToTraditionalChinese:"繁",msgToSimplifiedChinese:"簡"},noticeOutdate:void 0,highlight:{plugin:"highlighjs",highlightCopy:!0,highlightLang:!0,highlightHeightLimit:!1},copy:{success:"复制成功",error:"复制错误",noSupport:"浏览器不支持"},relativeDate:{homepage:!1,post:!1},runtime:"",date_suffix:{just:"刚刚",min:"分钟前",hour:"小时前",day:"天前",month:"个月前"},copyright:{limitCount:20,languages:{author:"作者: 寒兔丶",link:"链接: ",source:"来源: 麻辣兔头川菜馆",info:"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},lightbox:"fancybox",Snackbar:void 0,source:{justifiedGallery:{js:"https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.js",css:"https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.css"}},isPhotoFigcaption:!1,islazyload:!1,isAnchor:!0}</script><script id="config-diff">var GLOBAL_CONFIG_SITE={title:"数据结构和算法",isPost:!0,isHome:!1,isHighlightShrink:!1,isToc:!0,postUpdate:"2022-12-24 17:50:05"}</script><noscript><style>#nav{opacity:1}.justified-gallery img{opacity:1}#post-meta time,#recent-posts time{display:inline!important}</style></noscript><script>(e=>{e.saveToLocal={set:function(e,t,o){if(0===o)return;const n=864e5*o,a={value:t,expiry:(new Date).getTime()+n};localStorage.setItem(e,JSON.stringify(a))},get:function(e){const t=localStorage.getItem(e);if(!t)return;const o=JSON.parse(t);if(!((new Date).getTime()>o.expiry))return o.value;localStorage.removeItem(e)}},e.getScript=e=>new Promise(((t,o)=>{const n=document.createElement("script");n.src=e,n.async=!0,n.onerror=o,n.onload=n.onreadystatechange=function(){const e=this.readyState;e&&"loaded"!==e&&"complete"!==e||(n.onload=n.onreadystatechange=null,t())},document.head.appendChild(n)})),e.activateDarkMode=function(){document.documentElement.setAttribute("data-theme","dark"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#0d0d0d")},e.activateLightMode=function(){document.documentElement.setAttribute("data-theme","light"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#ffffff")};const t=saveToLocal.get("theme");"dark"===t?activateDarkMode():"light"===t&&activateLightMode();const o=saveToLocal.get("aside-status");void 0!==o&&("hide"===o?document.documentElement.classList.add("hide-aside"):document.documentElement.classList.remove("hide-aside"));/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)&&document.documentElement.classList.add("apple")})(window)</script><link rel="stylesheet" href="/css/custom.css"><link rel="stylesheet" href="/css/font.css"><link rel="stylesheet" href="/css/menu_center.css"><link rel="stylesheet" href="/css/rightside.css"><script src="/js/rightside.js"></script><script src="/js/changeMode.js"></script><link rel="stylesheet" href="/css/weather.css"><meta name="generator" content="Hexo 5.4.2"></head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="/img/avatar.png" onerror='onerror=null,src="/img/friend_404.gif"' alt="avatar"></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">5</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">6</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">4</div></a></div><hr><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i> <span>首页</span></a></div><div class="menus_item"><a class="site-page group hide" href="javascript:void(0);"><i class="fa-fw fas fa-scroll-torah"></i> <span>文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-timeline"></i> <span>时间轴</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i> <span>文章分类</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i> <span>标签大全</span></a></li><li><a class="site-page child" href="/random/"><i class="fa-fw fas fa-shuffle"></i> <span>随便看看</span></a></li></ul></div><div class="menus_item"><a class="site-page group hide" href="javascript:void(0);"><i class="fa-fw fas fa-heart"></i> <span>社交</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/link/"><i class="fa-fw fas fa-link"></i> <span>友链</span></a></li><li><a class="site-page child" href="/messageboard/"><i class="fa-fw fa fa-paper-plane"></i> <span>留言板</span></a></li></ul></div><div class="menus_item"><a class="site-page group hide" href="javascript:void(0);"><i class="fa-fw fas fa-gamepad"></i> <span>娱乐</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i> <span>音乐</span></a></li><li><a class="site-page child" href="/game/"><i class="fa-fw fas fa-chess-board"></i> <span>小游戏</span></a></li></ul></div><div class="menus_item"><a class="site-page group hide" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i> <span>关于</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/about/"><i class="fa-fw iconfont icon-wode"></i> <span>关于我</span></a></li><li><a class="site-page child" href="/site/"><i class="fa-fw iconfont icon-config"></i> <span>关于网站</span></a></li><li><a class="site-page child" href="/state/"><i class="fa-fw iconfont icon-dunpai"></i> <span>本站状态</span></a></li></ul></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image:url('/img/default_cover1.png')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">麻辣兔头川菜馆</a></span><div id="menus"><div class="nav-button" id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i></a></div><span id="translateBtn"><a class="nav-button" id="translateLink" type="button" title="简繁转换" name="简繁转换">繁</a></span><span id="changeMode"><a class="nav-button" id="darkmode" type="button" title="浅色和深色模式转换" name="浅色和深色模式转换" onclick="changeMode()"><i class="fas fa-adjust"></i></a></span><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i> <span>首页</span></a></div><div class="menus_item"><a class="site-page group hide" href="javascript:void(0);"><i class="fa-fw fas fa-scroll-torah"></i> <span>文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-timeline"></i> <span>时间轴</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i> <span>文章分类</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i> <span>标签大全</span></a></li><li><a class="site-page child" href="/random/"><i class="fa-fw fas fa-shuffle"></i> <span>随便看看</span></a></li></ul></div><div class="menus_item"><a class="site-page group hide" href="javascript:void(0);"><i class="fa-fw fas fa-heart"></i> <span>社交</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/link/"><i class="fa-fw fas fa-link"></i> <span>友链</span></a></li><li><a class="site-page child" href="/messageboard/"><i class="fa-fw fa fa-paper-plane"></i> <span>留言板</span></a></li></ul></div><div class="menus_item"><a class="site-page group hide" href="javascript:void(0);"><i class="fa-fw fas fa-gamepad"></i> <span>娱乐</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i> <span>音乐</span></a></li><li><a class="site-page child" href="/game/"><i class="fa-fw fas fa-chess-board"></i> <span>小游戏</span></a></li></ul></div><div class="menus_item"><a class="site-page group hide" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i> <span>关于</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/about/"><i class="fa-fw iconfont icon-wode"></i> <span>关于我</span></a></li><li><a class="site-page child" href="/site/"><i class="fa-fw iconfont icon-config"></i> <span>关于网站</span></a></li><li><a class="site-page child" href="/state/"><i class="fa-fw iconfont icon-dunpai"></i> <span>本站状态</span></a></li></ul></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">数据结构和算法</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2022-12-24T09:25:45.738Z" title="发表于 2022-12-24 17:25:45">2022-12-24</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2022-12-24T09:50:05.254Z" title="更新于 2022-12-24 17:50:05">2022-12-24</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" data-flag-title="数据结构和算法"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="常用数据结构"><a href="#常用数据结构" class="headerlink" title="常用数据结构"></a>常用数据结构</h1><p><code>数据结构 考研 找工作 记忆性、理解性 代码实现 证明理解了的最高表现形式 代码实现对记忆、理解 促进作用 实现要比记忆、理解难得多 记忆、理解</code></p><ul><li>数组（动态化）</li><li>栈 递归 斐波那契数列</li><li>链表 增删方便 查找费时 适用于频繁增加或者删除的场景</li><li>图 邻接矩阵 邻接表</li><li>散列表 哈希冲突</li><li>队列 多线程阻塞</li><li>树 平衡二叉树、红黑树（HashMap底层代码）、B+树（mysql索引）</li><li>堆 特殊的树 排序</li></ul><h1 id="四种存储方式"><a href="#四种存储方式" class="headerlink" title="四种存储方式"></a>四种存储方式</h1><h2 id="顺序存储"><a href="#顺序存储" class="headerlink" title="顺序存储"></a>顺序存储</h2><p>在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。</p><p>特点：</p><ol><li>随机存取表中元素。</li><li>插入和删除操作需要移动元素。</li></ol><h2 id="链接存储"><a href="#链接存储" class="headerlink" title="链接存储"></a>链接存储</h2><p>在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。</p><p>特点：</p><ol><li>比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。</li><li>逻辑上相邻的节点物理上不必相邻。</li><li>插入、删除灵活 (不必移动节点，只要改变节点中的指针)。</li><li>查找结点时链式存储要比顺序存储慢。</li><li>每个结点是由数据域和指针域组成。</li></ol><h2 id="索引存储"><a href="#索引存储" class="headerlink" title="索引存储"></a>索引存储</h2><p>除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。</p><p>特点：</p><p>索引存储结构是用结点的索引号来确定结点存储地址，其优点是检索速度快，缺点是增加了附加的索引表,会占用较多的存储空间。</p><h2 id="散列存储"><a href="#散列存储" class="headerlink" title="散列存储"></a>散列存储</h2><p>散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。</p><p>散列法存储的基本思想是：由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储。</p><p>特点：</p><p>散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的，而不像在数组中的遍历过程，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置，这样的访问速度就省去了遍历数组的实现，因此时间复杂度可以认为为O(1)，而数组遍历的时间复杂度为O(n)。</p><h1 id="线性结构和非线性结构"><a href="#线性结构和非线性结构" class="headerlink" title="线性结构和非线性结构"></a>线性结构和非线性结构</h1><p>数据结构包括 <strong>线性结构</strong> 和 <strong>非线性结构</strong></p><h2 id="线性结构"><a href="#线性结构" class="headerlink" title="线性结构"></a>线性结构</h2><ol><li>线性结构作为最常用的数据结构，其特点是<strong>数据元素之间存在一对一</strong>的线性关系</li><li>线性结构有两种不同的存储结构，即<strong>顺序存储结构</strong>和<strong>链式存储结构</strong>。顺序存储的线性表称为顺序表，顺序表中的<strong>存储地址是连续的</strong></li><li>链式存储的线性表称为链表，链表中的<strong>存储地址不一定是连续的</strong>，元素节点中存放数据元素以及相邻元素的地址信息</li><li>线性结构常见的有:数组、队列、链表和栈，后面我们会详细讲解.</li></ol><h2 id="非线性结构"><a href="#非线性结构" class="headerlink" title="非线性结构"></a>非线性结构</h2><p>非线性结构包括：二维数组，多维数组，广义表，树结构，图结构</p><h1 id="稀疏数组"><a href="#稀疏数组" class="headerlink" title="稀疏数组"></a>稀疏数组</h1><h2 id="简介"><a href="#简介" class="headerlink" title="简介"></a>简介</h2><p>当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组</p><p>稀疏数组的处理方法是：</p><ol><li>记录数组一共有几行几列，有多少个不同的值</li><li>把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模</li></ol><p>实例：</p><p>稀疏数组一般是三列n行的动态二维数组</p><p>稀疏数组只有在稀疏数据时有优势</p><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">    row col val</span></span><br><span class="line"><span class="comment">  0	几行 几列 实际元素数</span></span><br><span class="line"><span class="comment">    1  第一个有效数据在哪一行哪一列</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line">  row col val</span><br><span class="line">  <span class="number">0</span>  <span class="number">11</span>  <span class="number">11</span>  <span class="number">2</span></span><br><span class="line">  <span class="number">1</span>   <span class="number">1</span>  <span class="number">2</span>   <span class="number">1</span></span><br><span class="line">  <span class="number">2</span>   <span class="number">2</span>  <span class="number">3</span>   <span class="number">2</span></span><br></pre></td></tr></table></figure><p>二维数组 转 稀疏数组 的思路</p><ol><li>遍历 原始二维数组，得到有效数据的个数sum</li><li>根据sum就可以创建稀疏数组<code>sparseArr int[sum+1][3]</code></li><li>将二维数组的有效数据存入到稀疏数组中</li></ol><p>稀疏数组 转 原始二维数组 的思路</p><ol><li>先读取稀疏数组的第一行，根据第一行的数据创建原始的二维数组，比如上面的 <code>chassArr2 = int[11][11]</code></li><li>再读取稀疏数组后几行的数据，并赋给 二位数组即可</li></ol><h2 id="应用实例"><a href="#应用实例" class="headerlink" title="应用实例"></a>应用实例</h2><ol><li>使用稀疏数组，来保留类似前面的二维数组（棋盘、地图等等）</li><li>把稀疏数组存盘，并且可以重新恢复成原来的二维数组</li></ol><h2 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Auther</span>: MFM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span>: 2022/3/12 - 03 - 12 - 8:42</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">sparseArr</span> &#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="comment">//创建一个11*11的原始二维数组</span></span><br><span class="line">        <span class="comment">//0 无子 1 黑子 2白子</span></span><br><span class="line">        <span class="type">int</span>[][] chessArr1 = <span class="keyword">new</span> <span class="title class_">int</span>[<span class="number">11</span>][<span class="number">11</span>];</span><br><span class="line">        chessArr1[<span class="number">1</span>][<span class="number">2</span>] = <span class="number">1</span>;</span><br><span class="line">        chessArr1[<span class="number">2</span>][<span class="number">3</span>] = <span class="number">2</span>;</span><br><span class="line">        <span class="comment">//输出原始数组</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span>[] arr : chessArr1) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> data : arr) &#123;</span><br><span class="line">                System.out.print(data + <span class="string">&quot; &quot;</span>);</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println();</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//把原始数组 转换为 稀疏数组</span></span><br><span class="line">        System.out.println();</span><br><span class="line">        <span class="type">int</span>[][] arr = ArrChange(chessArr1);</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            System.out.println(Arrays.toString(arr[i]));</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//把稀疏数组 转换为 原始数组</span></span><br><span class="line">        System.out.println();</span><br><span class="line">        <span class="type">int</span>[][] ints = ArrChanges(arr);</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; ints.length; i++) &#123;</span><br><span class="line">            System.out.println(Arrays.toString(ints[i]));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//二维数组 转 稀疏数组</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span>[][] ArrChange(<span class="type">int</span>[][] arr) <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (arr == <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;传入二维数组错误&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> <span class="variable">sum</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; arr[i].length; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (arr[i][j] != <span class="number">0</span>) &#123;</span><br><span class="line">                    sum++;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//创建对应的稀疏数组</span></span><br><span class="line">        <span class="type">int</span>[][] sparseArr = <span class="keyword">new</span> <span class="title class_">int</span>[sum + <span class="number">1</span>][<span class="number">3</span>];</span><br><span class="line">        <span class="comment">//00 是行数 01 是列数 02 是有效数据数</span></span><br><span class="line">        sparseArr[<span class="number">0</span>][<span class="number">0</span>] = arr.length;</span><br><span class="line">        sparseArr[<span class="number">0</span>][<span class="number">1</span>] = arr[<span class="number">0</span>].length;</span><br><span class="line">        sparseArr[<span class="number">0</span>][<span class="number">2</span>] = sum;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//遍历二维数组，将非零的值存放到稀疏数组中</span></span><br><span class="line">        sum = <span class="number">0</span>;<span class="comment">//用来记录是第几个非零数据</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; arr[i].length; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (arr[i][j] != <span class="number">0</span>) &#123;</span><br><span class="line">                    sum++;</span><br><span class="line">                    sparseArr[sum][<span class="number">0</span>] = i;</span><br><span class="line">                    sparseArr[sum][<span class="number">1</span>] = j;</span><br><span class="line">                    sparseArr[sum][<span class="number">2</span>] = arr[i][j];</span><br><span class="line"></span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> sparseArr;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//稀疏数组 转 二维数组</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span>[][] ArrChanges(<span class="type">int</span>[][] arr) <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (arr == <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;传入稀疏数组错误&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//读取行数和列数 创建新数组</span></span><br><span class="line">        <span class="type">int</span> row, col;</span><br><span class="line">        row = arr[<span class="number">0</span>][<span class="number">0</span>];</span><br><span class="line">        col = arr[<span class="number">0</span>][<span class="number">1</span>];</span><br><span class="line">        <span class="type">int</span>[][] sparseArr = <span class="keyword">new</span> <span class="title class_">int</span>[row][col];</span><br><span class="line"></span><br><span class="line">        <span class="comment">//先用0把新建的二维数组填满</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span>[] arr1 : sparseArr) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> a : arr1) &#123;</span><br><span class="line">                a = <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//根据稀疏数组中的坐标 将值放回原位</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">1</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            sparseArr[arr[i][<span class="number">0</span>]][arr[i][<span class="number">1</span>]] = arr[i][<span class="number">2</span>];</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> sparseArr;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">      <span class="comment">//扩充 将转换后的 稀疏数组 存入磁盘</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">save</span><span class="params">(<span class="type">int</span>[][] arr)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (arr == <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;数组为空&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//开启字符输出流</span></span><br><span class="line">        <span class="type">OutputStreamWriter</span> <span class="variable">osw</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">OutputStreamWriter</span>(<span class="keyword">new</span> <span class="title class_">FileOutputStream</span>(<span class="string">&quot;./JavaDataStruct/NewFile/data.txt&quot;</span>));</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            <span class="type">String</span> <span class="variable">s</span> <span class="operator">=</span> Arrays.toString(arr[i]);</span><br><span class="line">            osw.write(s + <span class="string">&quot;\n&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        osw.close();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//扩充 读取磁盘中的 稀疏数组 并 转换为 二维数组 进行读取</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> String[] load() <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        String[] arr = <span class="literal">null</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//开启字符输入流</span></span><br><span class="line">       <span class="type">RandomAccessFile</span> <span class="variable">raf</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">RandomAccessFile</span>(<span class="keyword">new</span> <span class="title class_">File</span>(<span class="string">&quot;./JavaDataStruct/NewFile/data.txt&quot;</span>),<span class="string">&quot;r&quot;</span>);</span><br><span class="line"></span><br><span class="line">        arr = <span class="keyword">new</span> <span class="title class_">String</span>[<span class="number">11</span>];</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; <span class="number">11</span>; i++) &#123;</span><br><span class="line">            arr[i] = raf.readLine();</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (arr == <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;读取错误，数组为空&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> arr;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="数组"><a href="#数组" class="headerlink" title="数组"></a>数组</h1><p>数组的二次封装</p><p>用一个类来二次封装数组</p><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Auther</span>: MFM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span>: 2022/3/10 - 03 - 10 - 11:57</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">ArrayDemo</span>&lt;E&gt; &#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     *   数组</span></span><br><span class="line"><span class="comment">     *   属性：容量 实际数量 是否为空</span></span><br><span class="line"><span class="comment">     *   方法：增删改查</span></span><br><span class="line"><span class="comment">     *   额外功能：自动扩容</span></span><br><span class="line"><span class="comment">     * */</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">//底层 静态数组</span></span><br><span class="line">    <span class="keyword">private</span> E[] data;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//实际数量</span></span><br><span class="line">    <span class="keyword">private</span> <span class="type">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//获得实际数量</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getSize</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> size;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//获得容量</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getCapacity</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> data.length;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//空构造函数</span></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">ArrayDemo</span><span class="params">(<span class="type">int</span> capacity)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        setCapacity(capacity);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//初始化 设置容量</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setCapacity</span><span class="params">(<span class="type">int</span> capacity)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (capacity &lt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;索引越界&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        data = (E[]) <span class="keyword">new</span> <span class="title class_">Object</span>[capacity];</span><br><span class="line">        <span class="comment">//初始化时容量为0</span></span><br><span class="line">        size = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//判断是否为空 是null显示true 不是null显示false</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">isNull</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> data.length == <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//增加功能</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">addData</span><span class="params">(<span class="type">int</span> index, E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (index &lt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;索引越界&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (index &gt; data.length) &#123;</span><br><span class="line">            E[] newData = (E[]) <span class="keyword">new</span> <span class="title class_">Object</span>[data.length + <span class="number">10</span>];</span><br><span class="line"></span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; size; i++) &#123;</span><br><span class="line">                newData[i] = data[i];</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            data = newData;</span><br><span class="line">        &#125;</span><br><span class="line">        data[index] = e;</span><br><span class="line">        size++;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//在数组头部增加元素</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">addFirst</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (size &lt; getCapacity()) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> size; i &gt; <span class="number">0</span>; i--) &#123;</span><br><span class="line">                data[i] = data[i - <span class="number">1</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            data[<span class="number">0</span>] = e;</span><br><span class="line">            size++;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//扩容</span></span><br><span class="line">            E[] newData = (E[]) <span class="keyword">new</span> <span class="title class_">Object</span>[data.length + <span class="number">10</span>];</span><br><span class="line"></span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; size; i++) &#123;</span><br><span class="line">                newData[i] = data[i];</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            data = newData;</span><br><span class="line">            <span class="comment">//扩容完毕</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> size; i &gt; <span class="number">0</span>; i--) &#123;</span><br><span class="line">                data[i + <span class="number">1</span>] = data[i];</span><br><span class="line">            &#125;</span><br><span class="line">            data[<span class="number">0</span>] = e;</span><br><span class="line">            size++;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//在数组尾部增加元素</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">addLast</span><span class="params">(E e)</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (size &lt; getCapacity()) &#123;</span><br><span class="line">            data[size] = e;</span><br><span class="line">            size++;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//扩容</span></span><br><span class="line">            E[] newData = (E[]) <span class="keyword">new</span> <span class="title class_">Object</span>[data.length + <span class="number">10</span>];</span><br><span class="line"></span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; size; i++) &#123;</span><br><span class="line">                newData[i] = data[i];</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            data = newData;</span><br><span class="line">            <span class="comment">//扩容完毕</span></span><br><span class="line">            data[size] = e;</span><br><span class="line">            size++;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//删除功能</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">deleteData</span><span class="params">(<span class="type">int</span> index)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (index&gt;size-<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;该索引不存在元素&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="type">E</span> <span class="variable">e</span> <span class="operator">=</span> seeData(index);</span><br><span class="line">        E[] newData = (E[]) <span class="keyword">new</span> <span class="title class_">Object</span>[data.length - <span class="number">1</span>];</span><br><span class="line">        <span class="keyword">if</span> (index + <span class="number">1</span> == data.length) &#123;</span><br><span class="line">            <span class="comment">//删除的是最后一个数据</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; newData.length; i++) &#123;</span><br><span class="line">                newData[i] = data[i];</span><br><span class="line">            &#125;</span><br><span class="line">            data = newData;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//删除的位置后面有元素</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; index; i++) &#123;</span><br><span class="line">                <span class="comment">//index 前元素复制</span></span><br><span class="line">                newData[i] = data[i];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> index; i &lt; data.length; i++) &#123;</span><br><span class="line">                <span class="comment">//index 后元素复制</span></span><br><span class="line">                newData[i - <span class="number">1</span>] = data[i];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        size--;</span><br><span class="line">        <span class="keyword">return</span> e;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//修改功能</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">changeData</span><span class="params">(<span class="type">int</span> index, E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        deleteData(index);</span><br><span class="line">        addData(index, e);</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查询功能</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">seeData</span><span class="params">(<span class="type">int</span> index)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (index &gt; data.length || index &lt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;索引越界&quot;</span>);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">return</span> data[index];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">find</span><span class="params">(E e)</span> &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; data.length; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (e.equals(data[i])) &#123;</span><br><span class="line"></span><br><span class="line">                <span class="comment">//找到该元素返回索引i</span></span><br><span class="line">                <span class="keyword">return</span> i;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//未找到该元素位置就返回-1</span></span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//找一堆 元素 传入一堆E 返回一个由索引构成的一个数组</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span>[] finds(E... es) &#123;</span><br><span class="line">        <span class="type">int</span>[] arr = <span class="keyword">new</span> <span class="title class_">int</span>[es.length];</span><br><span class="line">        <span class="type">int</span> <span class="variable">count</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; es.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; data.length; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (es[i].equals(data[j])) &#123;</span><br><span class="line">                    arr[count] = j;</span><br><span class="line">                    count++;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (i == count) &#123;</span><br><span class="line">                <span class="comment">//将-1存入索引数组中表示未找到</span></span><br><span class="line">                arr[count] = -<span class="number">1</span>;</span><br><span class="line">                count++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> arr;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="type">StringBuilder</span> <span class="variable">sb</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">StringBuilder</span>();</span><br><span class="line">        sb.append(<span class="string">&quot;ArrayDemo&#123;&quot;</span> + <span class="string">&quot;data=&quot;</span>);</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; size; i++) &#123;</span><br><span class="line">            sb.append(data[i]);</span><br><span class="line">            <span class="keyword">if</span> (i!=size-<span class="number">1</span>)&#123;</span><br><span class="line">                sb.append(<span class="string">&quot;,&quot;</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        sb.append(<span class="string">&quot;&#125;&quot;</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span>  sb.toString();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br></pre></td></tr></table></figure><h1 id="链表"><a href="#链表" class="headerlink" title="链表"></a>链表</h1><ul><li>数据存储在节点(Node)中</li><li>Node一般来说有：元素、后继(Next)</li><li>如果要实现双向链表就可以将Node增加前驱(Pre)</li><li>第一个节点前驱为Null，最后一个节点后继为Null</li><li>节点可以使用内部类来实现</li></ul><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Auther</span>: MFM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span>: 2022/3/12 - 03 - 12 - 17:45</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">LinkedDemo</span>&lt;E&gt; &#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * 链表</span></span><br><span class="line"><span class="comment">     * 属性：(前驱 元素 后继) 头节点 当前节点 实际数量 是否为空</span></span><br><span class="line"><span class="comment">     * 方法：增（头，尾，任意）删改查</span></span><br><span class="line"><span class="comment">     * */</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">class</span> <span class="title class_">Node</span>&lt;E&gt; &#123;</span><br><span class="line">        <span class="comment">//元素</span></span><br><span class="line">        <span class="keyword">private</span> E e;</span><br><span class="line">        <span class="comment">//前驱</span></span><br><span class="line">        <span class="keyword">private</span> Node Pre;</span><br><span class="line">        <span class="comment">//后继</span></span><br><span class="line">        <span class="keyword">private</span> Node Next;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(E e, Node pre, Node next)</span> &#123;</span><br><span class="line">            <span class="built_in">this</span>.e = e;</span><br><span class="line">            Pre = pre;</span><br><span class="line">            Next = next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//初始化只有一个节点 前后都为null</span></span><br><span class="line">        <span class="keyword">public</span> <span class="title function_">Node</span><span class="params">()</span> &#123;</span><br><span class="line">            <span class="built_in">this</span>(<span class="literal">null</span>, <span class="literal">null</span>, <span class="literal">null</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(E e)</span> &#123;</span><br><span class="line">            <span class="built_in">this</span>(e, <span class="literal">null</span>, <span class="literal">null</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(E e, Node next)</span> &#123;</span><br><span class="line">            <span class="built_in">this</span>(e, <span class="literal">null</span>, next);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="meta">@Override</span></span><br><span class="line">        <span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span> &#123;</span><br><span class="line">            <span class="type">StringBuilder</span> <span class="variable">sb</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">StringBuilder</span>();</span><br><span class="line">            sb.append(<span class="string">&quot;Node:E=&quot;</span> + e + <span class="string">&quot;,Pre=&quot;</span> + Pre + <span class="string">&quot;,Next=&quot;</span> + Next);</span><br><span class="line">            <span class="keyword">return</span> sb.toString();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//实际数量</span></span><br><span class="line">    <span class="keyword">private</span> <span class="type">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//头节点</span></span><br><span class="line">    <span class="keyword">private</span> Node head;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//当前节点</span></span><br><span class="line">    <span class="keyword">private</span> Node node;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">LinkedDemo</span><span class="params">()</span> &#123;</span><br><span class="line">        head = <span class="literal">null</span>;</span><br><span class="line">        size = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">LinkedDemo</span><span class="params">(Node head)</span> &#123;</span><br><span class="line">        <span class="built_in">this</span>.head = head;</span><br><span class="line">        size = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//增</span></span><br><span class="line">    <span class="comment">//增加到任意位置</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">add</span><span class="params">(E e, <span class="type">int</span> index)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (index &lt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;索引错误&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        Node&lt;E&gt; newNode = <span class="keyword">new</span> <span class="title class_">Node</span>&lt;&gt;(e);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (head == <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="comment">//如果没有头节点（原链表没有节点）</span></span><br><span class="line">            head = <span class="keyword">new</span> <span class="title class_">Node</span>&lt;&gt;(e);</span><br><span class="line">            node = head;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//index大于size时 直接将node放到链表最后</span></span><br><span class="line">        <span class="keyword">if</span> (index&gt;size)&#123;</span><br><span class="line">            addLast(e);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//当index为尾时</span></span><br><span class="line">        <span class="keyword">if</span> (index==size)&#123;</span><br><span class="line">            node = head;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; index; i++) &#123;</span><br><span class="line">                node = node.Next;</span><br><span class="line">            &#125;</span><br><span class="line">            node.Next = newNode;</span><br><span class="line">            newNode.Pre = node;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//将现在的节点node设置成头节点head</span></span><br><span class="line">        node = head;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; index; i++) &#123;</span><br><span class="line">            node = node.Next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//将index-1的节点的next赋予newNode newNode 的next就是node的next</span></span><br><span class="line">        newNode.Next = node.Next;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//将node.Next的Pre改成newNode</span></span><br><span class="line">        node.Next.Pre = newNode;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//再将node的next换成newNode 现在数据结构就是 node-&gt;newNode&lt;-&gt;node.next</span></span><br><span class="line">        node.Next = newNode;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//再将newNode的前驱变为node</span></span><br><span class="line">        newNode.Pre = node;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//增加完毕</span></span><br><span class="line">        size++;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//增加头部</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">addFirst</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (head==<span class="literal">null</span>)&#123;</span><br><span class="line">            head = <span class="keyword">new</span> <span class="title class_">Node</span>(e);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        node = head;</span><br><span class="line"></span><br><span class="line">        head = <span class="keyword">new</span> <span class="title class_">Node</span>(e);</span><br><span class="line"></span><br><span class="line">        head.Next = node;</span><br><span class="line"></span><br><span class="line">        node.Pre = head;</span><br><span class="line"></span><br><span class="line">        size++;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//增加尾部</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">addLast</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (head==<span class="literal">null</span>)&#123;</span><br><span class="line">            head = <span class="keyword">new</span> <span class="title class_">Node</span>(e);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        node = head;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; size; i++) &#123;</span><br><span class="line">            node = node.Next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="type">Node</span> <span class="variable">newNode</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Node</span>(e);</span><br><span class="line"></span><br><span class="line">        node.Next = newNode;</span><br><span class="line">        newNode.Pre = node;</span><br><span class="line"></span><br><span class="line">        size++;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">//删</span></span><br><span class="line">    <span class="comment">//根据索引删除node</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">delete</span><span class="params">(<span class="type">int</span> index)</span><span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">if</span> (head==<span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;链表内无内容无法删除&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        node = head;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; index; i++) &#123;</span><br><span class="line">            node = node.Next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//记录要删除的节点的值</span></span><br><span class="line">        <span class="type">E</span> <span class="variable">e</span> <span class="operator">=</span> (E)node.e;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//如果删除的节点是头节点</span></span><br><span class="line">        <span class="keyword">if</span> (index==<span class="number">0</span>)&#123;</span><br><span class="line">            node.Next.Pre =<span class="literal">null</span>;</span><br><span class="line">            node = node.Next;</span><br><span class="line">            <span class="keyword">return</span> e;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//node为将要删除的节点 将该节点的Pre的Next转为该节点的Next即可删除该节点</span></span><br><span class="line">        node.Pre.Next = node.Next;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> e;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//根据元素删除node</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">delete</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (head==<span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;链表内无内容无法删除&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        node = head;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; size; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (node.e.equals(e))&#123;</span><br><span class="line">                delete(i);</span><br><span class="line">                <span class="keyword">return</span> e;</span><br><span class="line">            &#125;</span><br><span class="line">            node = node.Next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//返回null表示没有找到该内容</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//改</span></span><br><span class="line">    <span class="comment">//根据索引修改</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">set</span><span class="params">(<span class="type">int</span> index,E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (head==<span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;链表内无内容无法修改&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        node = head;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; index; i++) &#123;</span><br><span class="line">            node = node.Next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        node.e = e;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> e;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查</span></span><br><span class="line">    <span class="comment">//根据索引查找</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">find</span><span class="params">(<span class="type">int</span> index)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (head==<span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;链表内无内容无法删除&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//当index大于size时 直接报错</span></span><br><span class="line">        <span class="keyword">if</span> (index&gt;size)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;该索引无节点&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        node = head;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; index; i++) &#123;</span><br><span class="line">            node = node.Next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> (E) node.e;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//根据元素查索引</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">find</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (head==<span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;链表内无内容无法删除&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        node = head;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; size; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (e.equals(node.e))&#123;</span><br><span class="line">                <span class="keyword">return</span> i;</span><br><span class="line">            &#125;</span><br><span class="line">            node = node.Next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//遍历所有链表节点的元素</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">findAll</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">if</span> (head==<span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;链表内无内容无法遍历&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        node = head;</span><br><span class="line"></span><br><span class="line">        System.out.print(node.e.toString()+<span class="string">&quot; &quot;</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; size; i++) &#123;</span><br><span class="line">            node = node.Next;</span><br><span class="line">            System.out.print(node.e.toString()+<span class="string">&quot; &quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getSize</span><span class="params">()</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">isEmpty</span><span class="params">()</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size==<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">super</span>.toString();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><h1 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h1><h2 id="底层数组"><a href="#底层数组" class="headerlink" title="底层数组"></a>底层数组</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Auther</span>: MFM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span>: 2022/3/14 - 03 - 14 - 15:43</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">ArrayStackDemo</span>&lt;E&gt; <span class="keyword">implements</span> <span class="title class_">Stack</span>&lt;E&gt;&#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * 栈</span></span><br><span class="line"><span class="comment">     * 只能从一端添加，只能从这一端取出，将这一端成为栈顶</span></span><br><span class="line"><span class="comment">     * 先进后出</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 方法：入栈（压栈） void push（E）</span></span><br><span class="line"><span class="comment">     *      出栈       E pop（）</span></span><br><span class="line"><span class="comment">     *       查看栈顶元素 E peek（）</span></span><br><span class="line"><span class="comment">     *       查看栈内有多少元素 int getSize（）</span></span><br><span class="line"><span class="comment">     *       查看栈是否为空 boolean isEmpty（）</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 扩充：如果对空栈进行出栈操作 称为 栈下溢</span></span><br><span class="line"><span class="comment">     *       如果size&gt;capacity 称为 栈上溢</span></span><br><span class="line"><span class="comment">     * */</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> ArrayDemo&lt;E&gt; array;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//指定容量构造函数</span></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">ArrayStackDemo</span><span class="params">(<span class="type">int</span> capacity)</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        array = <span class="keyword">new</span> <span class="title class_">ArrayDemo</span>&lt;&gt;(capacity);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//默认容量构造函数</span></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">ArrayStackDemo</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        array = <span class="keyword">new</span> <span class="title class_">ArrayDemo</span>&lt;&gt;(<span class="number">10</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//入栈</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">push</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">if</span>(array.getSize()==array.getCapacity())&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        array.addLast(e);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//出栈</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">pop</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.deleteData(array.getSize());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查看栈顶</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">peek</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.seeData(array.getSize());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查看栈内有多少元素</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getSize</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.getSize();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//判断栈内是否为空</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">isEmpty</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.getSize()==<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&quot;ArrayStackDemo&#123;&quot;</span> +</span><br><span class="line">                <span class="string">&quot;array=&quot;</span> + array +</span><br><span class="line">                <span class="string">&#x27;&#125;&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><h2 id="底层链表"><a href="#底层链表" class="headerlink" title="底层链表"></a>底层链表</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Auther</span>: MFM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span>: 2022/3/15 - 03 - 15 - 13:21</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">LinkedStackDemo</span>&lt;E&gt; <span class="keyword">implements</span> <span class="title class_">Stack</span>&lt;E&gt;&#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * 栈</span></span><br><span class="line"><span class="comment">     * 只能从一端添加，只能从这一端取出，将这一端成为栈顶</span></span><br><span class="line"><span class="comment">     * 先进后出</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 方法：入栈（压栈） void push（E）</span></span><br><span class="line"><span class="comment">     *      出栈       E pop（）</span></span><br><span class="line"><span class="comment">     *       查看栈顶元素 E peek（）</span></span><br><span class="line"><span class="comment">     *       查看栈内有多少元素 int getSize（）</span></span><br><span class="line"><span class="comment">     *       查看栈是否为空 boolean isEmpty（）</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 扩充：如果对空栈进行出栈操作 称为 栈下溢</span></span><br><span class="line"><span class="comment">     *       如果size&gt;capacity 称为 栈上溢</span></span><br><span class="line"><span class="comment">     * */</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">//底层链表</span></span><br><span class="line">    <span class="keyword">private</span> LinkedDemo&lt;E&gt; linked;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//压栈</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">push</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (linked.getSize()&gt;<span class="number">10</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        linked.addLast(e);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//出栈</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">pop</span><span class="params">()</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (linked.getSize()==<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">return</span> linked.delete(linked.getSize());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查看栈顶</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">peek</span><span class="params">()</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">return</span> linked.find(linked.getSize());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//获得栈内元素</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getSize</span><span class="params">()</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">return</span> linked.getSize();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//判断是否为空</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">isEmpty</span><span class="params">()</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">return</span> linked.getSize()==<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h1><h2 id="底层数组-1"><a href="#底层数组-1" class="headerlink" title="底层数组"></a>底层数组</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Auther</span>: MFM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span>: 2022/3/14 - 03 - 14 - 17:22</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">ArrayQueueDemo</span>&lt;E&gt; <span class="keyword">implements</span> <span class="title class_">Queue</span>&lt;E&gt;&#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * 队列</span></span><br><span class="line"><span class="comment">     * 只能从一端进从另一端出</span></span><br><span class="line"><span class="comment">     * 先进先出</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 方法；入队 void enqueue(E)</span></span><br><span class="line"><span class="comment">     *       出队  E dequeue()</span></span><br><span class="line"><span class="comment">     *       查看队首元素  E getFront()</span></span><br><span class="line"><span class="comment">     *       查看对内元素数量 int getSize()</span></span><br><span class="line"><span class="comment">     *       判断对内元素是否为空  boolean isEmpty()</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 扩充：如果对空队进行出队 称为 队列下溢</span></span><br><span class="line"><span class="comment">     *       如果size&gt;capacity 称为 队列下溢</span></span><br><span class="line"><span class="comment">     * */</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> ArrayDemo&lt;E&gt; array;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//构造函数默认capacity为10</span></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">ArrayQueueDemo</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        array = <span class="keyword">new</span> <span class="title class_">ArrayDemo</span>&lt;&gt;(<span class="number">10</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//构造函数指定capacity</span></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">ArrayQueueDemo</span><span class="params">(<span class="type">int</span> capacity)</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        array = <span class="keyword">new</span> <span class="title class_">ArrayDemo</span>&lt;&gt;(capacity);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">enqueue</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        array.addFirst(e);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">dequeue</span><span class="params">()</span>  <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">if</span> (getSize()==<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> array.deleteData(array.getSize());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">getFront</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.seeData(<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getSize</span><span class="params">()</span>  <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.getSize();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">isEmpty</span><span class="params">()</span>  <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.getSize()==<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&quot;ArrayQueueDemo&#123;&quot;</span> +</span><br><span class="line">                <span class="string">&quot;array=&quot;</span> + array +</span><br><span class="line">                <span class="string">&#x27;&#125;&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="底层链表-1"><a href="#底层链表-1" class="headerlink" title="底层链表"></a>底层链表</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Auther</span>: MFM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span>: 2022/3/15 - 03 - 15 - 13:34</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">LinkedQueueDemo</span>&lt;E&gt; <span class="keyword">implements</span> <span class="title class_">Queue</span>&lt;E&gt;&#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * 队列</span></span><br><span class="line"><span class="comment">     * 只能从一端进从另一端出</span></span><br><span class="line"><span class="comment">     * 先进先出</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 方法；入队 void enqueue(E)</span></span><br><span class="line"><span class="comment">     *       出队  E dequeue()</span></span><br><span class="line"><span class="comment">     *       查看队首元素  E getFront()</span></span><br><span class="line"><span class="comment">     *       查看对内元素数量 int getSize()</span></span><br><span class="line"><span class="comment">     *       判断对内元素是否为空  boolean isEmpty()</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 扩充：如果对空队进行出队 称为 队列下溢</span></span><br><span class="line"><span class="comment">     *       如果size&gt;capacity 称为 队列下溢</span></span><br><span class="line"><span class="comment">     * */</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">//底层链表</span></span><br><span class="line">    <span class="keyword">private</span> LinkedDemo&lt;E&gt; linked;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//入队</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">enqueue</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (linked.getSize()&gt;<span class="number">10</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        linked.addLast(e);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//出队</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">dequeue</span><span class="params">()</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">if</span> (linked.getSize()==<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> linked.delete(<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查看队首元素</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">getFront</span><span class="params">()</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">return</span> linked.find(<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查看对内元素数量</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getSize</span><span class="params">()</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">return</span> linked.getSize();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//判断对内是否为空</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">isEmpty</span><span class="params">()</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        <span class="keyword">return</span> linked.getSize()==<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="扩充：双向队列"><a href="#扩充：双向队列" class="headerlink" title="扩充：双向队列"></a>扩充：双向队列</h2><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Auther</span>: MFM</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span>: 2022/3/14 - 03 - 14 - 18:33</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span>: 1.0</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">DoubleArrayQueue</span>&lt;E&gt; &#123;</span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">    * 双向队列</span></span><br><span class="line"><span class="comment">    * */</span></span><br><span class="line">    <span class="comment">//底层数组</span></span><br><span class="line">    <span class="keyword">private</span> ArrayDemo&lt;E&gt; array;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//以左为队首 入队</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">enqueueL</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        array.addFirst(e);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//以右为队首 入队</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">enqueueR</span><span class="params">(E e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">        array.addLast(e);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//以左左为队首 出队</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">dequeueL</span><span class="params">()</span>  <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">if</span> (getSize()==<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> array.deleteData(array.getSize());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//以右为队首 出队</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">dequeueR</span><span class="params">()</span>  <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">if</span> (getSize()==<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> array.deleteData(<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//以左为队首 查看队首元素</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">getFrontL</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.seeData(<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//以右为队首 查看队首元素</span></span><br><span class="line">    <span class="keyword">public</span> E <span class="title function_">getFrontR</span><span class="params">()</span> <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.seeData(array.getSize());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//获得队列元素</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getSize</span><span class="params">()</span>  <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.getSize();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//判断是否为空</span></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">isEmpty</span><span class="params">()</span>  <span class="keyword">throws</span> Exception&#123;</span><br><span class="line">        <span class="keyword">return</span> array.getSize()==<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&quot;DoubleArrayQueueDemo&#123;&quot;</span> +</span><br><span class="line">                <span class="string">&quot;array=&quot;</span> + array +</span><br><span class="line">                <span class="string">&#x27;&#125;&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h1 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h1><h2 id="介绍"><a href="#介绍" class="headerlink" title="介绍"></a>介绍</h2><p>排序算法，将一组数据，按照指定的顺序进行排列的过程</p><h2 id="分类和算法复杂度"><a href="#分类和算法复杂度" class="headerlink" title="分类和算法复杂度"></a>分类和算法复杂度</h2><p><img src="/../imags/data%20structure&algorithm/image-20221224174922811.png" alt="image-20221224174922811"></p><p>相关概念：</p><ol><li><strong>稳定</strong>：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。</li><li><strong>不稳定</strong>：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。</li><li><strong>时间复杂度</strong>：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。</li><li><strong>空间复杂度：</strong>是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。</li></ol><h2 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h2><p>冒泡排序是一种简单的排序，一次比较两个元素，如果顺序错误，那么就进行交换，直到不需要交换为止。</p><p>因为数越大（越小）的元素经过交换就会想水泡一样慢慢浮出水面（数列的顶端）</p><h3 id="描述"><a href="#描述" class="headerlink" title="描述"></a>描述</h3><ol><li>比较相邻的数，如果第一个比第二个大就把他们交换</li><li>对数列中每一对相邻元素做相同操作，从第一对到结尾的最后一对，这样的话，最后的元素会是数列中最大的数</li><li>针对所有的元素重复以上步骤，除了最后一个</li><li>重复1-3，直至排序完成</li></ol><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//冒泡排序</span></span><br><span class="line"><span class="keyword">public</span>  <span class="keyword">void</span> <span class="title function_">BubbleSort</span><span class="params">(<span class="type">int</span>[] arr)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="type">int</span> <span class="variable">length</span> <span class="operator">=</span> arr.length;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (length!=<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; length-<span class="number">1</span>; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (arr[j]&gt;arr[j+<span class="number">1</span>])&#123;</span><br><span class="line">                <span class="type">int</span> <span class="variable">e</span> <span class="operator">=</span> arr[j];</span><br><span class="line">                arr[j] = arr[j+<span class="number">1</span>];</span><br><span class="line">                arr[j+<span class="number">1</span>] = e;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        length--;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h2><p>快速排序的基本思想：通过一次排序将待排序数列分割成两个部分，其中一部分的值要比另一部分要小。接下来，则可分别对这两部分数列进行排序，使得整个序列有序。对于绝大部分数列来说，快速排序总是优于归并排序。</p><h3 id="描述-1"><a href="#描述-1" class="headerlink" title="描述"></a>描述</h3><ol><li>选取基准值</li><li>设置两边变量i和j i++ j– 当 arr[i]&gt;pivot 或者 arrp[j]&lt;pivot 时 将i和j交换后继续遍历</li><li>单路排序 当 i==j 时停下 和基准值交换后 让基准值左边和右边分别 递归 排序</li><li>双路排序 当 i&gt;j 或者 i==j 时 让i在基准值后 j在基准值前 后 在进行递归 排序</li></ol><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//单路排序</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">QuickSort</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> start, <span class="type">int</span> end)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//当出现 start &gt; end 时 无法排序（start和end之间 只有一个数时） 直接返回</span></span><br><span class="line">    <span class="keyword">if</span> (start &gt; end) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="type">int</span> <span class="variable">l</span> <span class="operator">=</span> start;</span><br><span class="line">    <span class="type">int</span> <span class="variable">r</span> <span class="operator">=</span> end;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//基准数一直为左</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">pivot</span> <span class="operator">=</span> arr[start];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (l != r) &#123;</span><br><span class="line">        <span class="comment">//先右往左循环</span></span><br><span class="line">        <span class="keyword">while</span> (arr[r] &gt;= pivot &amp;&amp; l &lt; r) &#123;</span><br><span class="line">            r--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//再左往右循环</span></span><br><span class="line">        <span class="keyword">while</span> (arr[l] &lt; pivot &amp;&amp; l &lt; r) &#123;</span><br><span class="line">            l++;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        change(arr, l, r);</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//跳出循环意味着上述条件已经不成立了 不成立代表 l=j</span></span><br><span class="line"></span><br><span class="line">    change(arr, start, l);</span><br><span class="line"></span><br><span class="line">    QuickSort(arr, start, l - <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">    QuickSort(arr, l + <span class="number">1</span>, end);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//双路快排</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">DQuickSort</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> start, <span class="type">int</span> end)</span> &#123;</span><br><span class="line">    <span class="type">int</span> <span class="variable">l</span> <span class="operator">=</span> start;</span><br><span class="line">    <span class="type">int</span> <span class="variable">r</span> <span class="operator">=</span> end;</span><br><span class="line"></span><br><span class="line">    <span class="type">int</span> <span class="variable">pivot</span> <span class="operator">=</span> arr[(start + end) / <span class="number">2</span>];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (l &lt; r) &#123;</span><br><span class="line">        <span class="keyword">while</span> (arr[l] &lt; pivot) &#123;</span><br><span class="line">            l++;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (arr[r] &gt; pivot) &#123;</span><br><span class="line">            r--;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (l &gt;= r) &#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        change(arr, l, r);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//防止两个等于pivot的值一直压栈导致栈溢出</span></span><br><span class="line">        <span class="keyword">if</span> (arr[l] == pivot) &#123;</span><br><span class="line">            r--;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (arr[r] == pivot) &#123;</span><br><span class="line">            l++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//基准点排除 如果不排除基准点 就会 在还剩两个元素时 无限压栈</span></span><br><span class="line">    <span class="keyword">if</span> (l == r) &#123;</span><br><span class="line">        l++;</span><br><span class="line">        r--;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (r &gt; start) &#123;</span><br><span class="line">        DQuickSort(arr, start, r);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (end &gt; l) &#123;</span><br><span class="line">        DQuickSort(arr, l, end);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="简单插入排序"><a href="#简单插入排序" class="headerlink" title="简单插入排序"></a>简单插入排序</h2><p>插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。</p><h3 id="描述-2"><a href="#描述-2" class="headerlink" title="描述"></a>描述</h3><ol><li>从第一个元素开始，该元素可以认为已经被排序；</li><li>取出下一个元素，在已经排序的元素序列中从后向前扫描；</li><li>如果该元素（已排序）大于新元素，将该元素移到下一位置；</li><li>重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；</li><li>将新元素插入到该位置后；</li><li>重复步骤2~5。</li></ol><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//简单插入排序</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">simpleInsertionSort</span><span class="params">(<span class="type">int</span>[] arr)</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (arr == <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//从索引1 开始 一直到数组末尾</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">1</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            <span class="comment">//提供变量 保存临时数据</span></span><br><span class="line">            <span class="type">int</span> <span class="variable">e</span> <span class="operator">=</span> arr[i];</span><br><span class="line">            <span class="comment">//从i往前找符合条件的数</span></span><br><span class="line">            <span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> i;</span><br><span class="line"></span><br><span class="line">            <span class="comment">//若不符合条件 先复制数组 当都没有arr[index - 1]&lt;e 的数说明 原arr[i]最小 放到最前面 此时index=0 arr[index] = e</span></span><br><span class="line">            <span class="keyword">while</span> (index &gt; <span class="number">0</span> &amp;&amp; arr[index - <span class="number">1</span>] &gt; e) &#123;</span><br><span class="line">                arr[index] = arr[index - <span class="number">1</span>];</span><br><span class="line">                index--;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            <span class="comment">//如果index没有移动说明 arr[i] 为最大的数最大的数直接放在排好序的数组中不用再赋值</span></span><br><span class="line">            <span class="keyword">if</span> (index != i) &#123;</span><br><span class="line">                arr[index] = e;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure><h2 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h2><p>把元素按照下标的一定增量分组，一般情况下，初始分组为length/2，对每组使用直接插入排序算法排序，随着增量逐渐渐少，每组包含的元素越来越多，当增量减至为1的时候，整个序列恰好是一组，算法终止</p><h3 id="描述-3"><a href="#描述-3" class="headerlink" title="描述"></a>描述</h3><p>先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：</p><ol><li>选择一个增量序列t1，t2，…，tk，其中ti&gt;tj，tk=1；</li><li>按增量序列个数k，对序列进行k 趟排序；</li><li>每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。</li></ol><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//希尔排序</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">shellSort</span><span class="params">(<span class="type">int</span>[] arr)</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (arr==<span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//增量分组 一直到1为止 数组长度奇偶不影响排序</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> arr.length/<span class="number">2</span>; i &gt; <span class="number">0</span>; i/=<span class="number">2</span>) &#123;</span><br><span class="line">            <span class="comment">//每组都做插入排序</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> i; j &lt; arr.length; j++) &#123;</span><br><span class="line"></span><br><span class="line">                <span class="type">int</span> <span class="variable">e</span> <span class="operator">=</span> arr[j];</span><br><span class="line"></span><br><span class="line">                <span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> j;</span><br><span class="line"></span><br><span class="line">                <span class="keyword">while</span> (index - i &gt;= <span class="number">0</span> &amp;&amp; e &lt; arr[index - i])&#123;</span><br><span class="line">                    arr[index] = arr[index - i];</span><br><span class="line">                    index-=i;</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                <span class="keyword">if</span> (index != j)&#123;</span><br><span class="line">                    arr[index] = e;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure><h2 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h2><p>选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。</p><h3 id="描述-4"><a href="#描述-4" class="headerlink" title="描述"></a>描述</h3><p>n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：</p><ol><li>初始状态：无序区为R[1..n]，有序区为空；</li><li>第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；</li><li>n-1趟结束，数组有序化了。</li></ol><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//简单选择排序</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">selectSort</span><span class="params">(<span class="type">int</span>[] arr)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//将所有的数遍历并排放</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt;arr.length ; i++) &#123;</span><br><span class="line">        <span class="comment">//存放最小数的索引</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">minNum</span> <span class="operator">=</span> i;</span><br><span class="line">        <span class="comment">//遍历出最小的数的索引</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> i; j &lt; arr.length; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (arr[j]&lt;arr[minNum])&#123;</span><br><span class="line">                minNum = j;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//交换最小数和已排序后一位</span></span><br><span class="line">        <span class="keyword">new</span> <span class="title class_">ChangeSort</span>().change(arr,minNum,i);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h2><p>堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。</p><h3 id="描述-5"><a href="#描述-5" class="headerlink" title="描述"></a>描述</h3><ol><li>将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；</li><li>将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]&lt;=R[n]；</li><li>由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。</li></ol><p>第i个节点的子节点（如果存在的话）为 2i+1 和 2i+2 父节点为 （i - 1）/ 2</p><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">heapSort</span><span class="params">(<span class="type">int</span>[] arr)</span>&#123;</span><br><span class="line">        <span class="comment">//将arr作为待排序数组 (arr.length-1)/2 为最后一个非叶子节点 并从后往前开始调整 arr.length 要对数组中所有元素进行调整</span></span><br><span class="line">        heapSort(arr,(arr.length-<span class="number">1</span>-<span class="number">1</span>)/<span class="number">2</span>,arr.length);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 将无序数组转换为大根堆</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> arr 需要转换的无序数组</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> i   从哪一个非叶子节点开始调整</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> n   对多少元素进行调整</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">heapSort</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> i,<span class="type">int</span> n)</span>&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">count</span> <span class="operator">=</span> n;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">k</span> <span class="operator">=</span> <span class="number">0</span>; k &lt; n-<span class="number">1</span>; k++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> i; j &gt;= <span class="number">0</span>; j--) &#123;</span><br><span class="line">                maxInRoot(arr,j,count);</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">new</span> <span class="title class_">ChangeSort</span>().change(arr,<span class="number">0</span>,count-<span class="number">1</span>);</span><br><span class="line">            count--;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 找出 以i为根的最小树中的最大值</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> arr   转化为数的数组</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> i     当前根</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">maxInRoot</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> i,<span class="type">int</span> n)</span>&#123;</span><br><span class="line">        <span class="type">int</span> <span class="variable">kidL</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="type">int</span> <span class="variable">kidR</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span> ( <span class="number">2</span> * i + <span class="number">2</span> &lt; n)&#123;</span><br><span class="line">            kidL = <span class="number">2</span> * i + <span class="number">1</span>;</span><br><span class="line">            kidR = <span class="number">2</span> * i + <span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> ( <span class="number">2</span> * i + <span class="number">1</span> &lt; n)&#123;</span><br><span class="line">            kidL = <span class="number">2</span> * i + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (kidL !=<span class="number">0</span> &amp;&amp; arr[kidL] &gt; arr[i] )&#123;</span><br><span class="line">            <span class="type">int</span> <span class="variable">num</span> <span class="operator">=</span> arr[kidL];</span><br><span class="line">            arr[kidL] = arr[i];</span><br><span class="line">            arr[i] = num;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (kidR !=<span class="number">0</span> &amp;&amp; arr[kidR] &gt; arr[i])&#123;</span><br><span class="line">            <span class="type">int</span> <span class="variable">num</span> <span class="operator">=</span> arr[kidR];</span><br><span class="line">            arr[kidR] = arr[i];</span><br><span class="line">            arr[i] = num;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure><h2 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h2><p>归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。</p><h3 id="描述-6"><a href="#描述-6" class="headerlink" title="描述"></a>描述</h3><ol><li>把长度为n的输入序列分成两个长度为n/2的子序列；</li><li>将子序列分为最小单元后再开始排列</li><li>分别将两个子序列进行排序</li><li>将两个排序好的子序列合并成一个最终的排序序列。</li></ol><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">MergeSort</span><span class="params">(<span class="type">int</span>[] arr)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr==<span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span>[] ints = MergeSort(arr, <span class="number">0</span>, arr.length - <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">        System.arraycopy(ints,<span class="number">0</span>,arr,<span class="number">0</span>,arr.length);</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span>[] MergeSort(<span class="type">int</span>[] arr1,<span class="type">int</span> start,<span class="type">int</span> end)&#123;</span><br><span class="line">        <span class="keyword">if</span> (start&gt;=end)&#123;</span><br><span class="line">            <span class="keyword">return</span> arr1;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> (start+end)/<span class="number">2</span>;</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span>[] arrA = <span class="keyword">new</span> <span class="title class_">int</span>[index-start+<span class="number">1</span>];</span><br><span class="line">        <span class="type">int</span>[] arrB = <span class="keyword">new</span> <span class="title class_">int</span>[end - index];</span><br><span class="line">        System.arraycopy(arr1,start,arrA,<span class="number">0</span>,index+<span class="number">1</span>);</span><br><span class="line">        System.arraycopy(arr1,index+<span class="number">1</span>,arrB,<span class="number">0</span>,end-index);</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="type">int</span>[] intsA = MergeSort(arrA, <span class="number">0</span>, arrA.length-<span class="number">1</span>);</span><br><span class="line">        <span class="type">int</span>[] intsB = MergeSort(arrB, <span class="number">0</span>, arrB.length-<span class="number">1</span>);</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span>[] returnInts = MergeSort(intsA, intsB);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> returnInts;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span>[] MergeSort(<span class="type">int</span>[] l,<span class="type">int</span>[] r)&#123;</span><br><span class="line">        <span class="type">int</span>[] ints = <span class="keyword">new</span> <span class="title class_">int</span>[l.length+r.length];</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="type">int</span> <span class="variable">lIndex</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">        <span class="type">int</span> <span class="variable">rIndex</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">       <span class="keyword">while</span> (lIndex&lt;l.length || rIndex&lt;r.length)&#123;</span><br><span class="line">           <span class="keyword">if</span> (rIndex == r.length)&#123;</span><br><span class="line">               ints[index] = l[lIndex];</span><br><span class="line">               index++;</span><br><span class="line">               lIndex++;</span><br><span class="line">           &#125;<span class="keyword">else</span> <span class="keyword">if</span> (lIndex == l.length)&#123;</span><br><span class="line">               ints[index] = r[rIndex];</span><br><span class="line">               index++;</span><br><span class="line">               rIndex++;</span><br><span class="line">           &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">               <span class="keyword">if</span> (l[lIndex]&lt;r[rIndex])&#123;</span><br><span class="line">                   ints[index] = l[lIndex];</span><br><span class="line">                   index++;</span><br><span class="line">                   lIndex++;</span><br><span class="line">               &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                   ints[index] = r[rIndex];</span><br><span class="line">                   index++;</span><br><span class="line">                   rIndex++;</span><br><span class="line">               &#125;</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> ints;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure><h2 id="计数排序"><a href="#计数排序" class="headerlink" title="计数排序"></a>计数排序</h2><p>计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。</p><h3 id="描述-7"><a href="#描述-7" class="headerlink" title="描述"></a>描述</h3><ul><li>找出待排序的数组中最大和最小的元素；</li><li>统计数组中每个值为i的元素出现的次数，存入数组C的第i项；</li><li>对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；</li><li>反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。</li></ul><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">countSort</span><span class="params">(<span class="type">int</span>[] arr)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (arr == <span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span> <span class="variable">maxNum</span> <span class="operator">=</span> arr[<span class="number">0</span>];</span><br><span class="line">        <span class="type">int</span> <span class="variable">minNum</span> <span class="operator">=</span> arr[<span class="number">0</span>];</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> num:arr) &#123;</span><br><span class="line">            <span class="keyword">if</span> (maxNum &lt; num)&#123;</span><br><span class="line">                maxNum = num;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (minNum &gt; num)&#123;</span><br><span class="line">                minNum = num;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        System.out.println(minNum + <span class="string">&quot; &quot;</span> +maxNum);</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span>[] sortedArr = <span class="keyword">new</span> <span class="title class_">int</span>[maxNum - minNum + <span class="number">1</span>];</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> minNum; i &lt; maxNum+<span class="number">1</span>; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; arr.length; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (arr[j] == i)&#123;</span><br><span class="line">                    sortedArr[i-minNum]++;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span>[] finArr = <span class="keyword">new</span> <span class="title class_">int</span>[arr.length];</span><br><span class="line"></span><br><span class="line">        <span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; sortedArr.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; sortedArr[i]; j++) &#123;</span><br><span class="line"></span><br><span class="line">                    finArr[index++] = minNum + i;</span><br><span class="line"></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        System.arraycopy(finArr,<span class="number">0</span>,arr,<span class="number">0</span>,arr.length);</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure><h2 id="桶排序"><a href="#桶排序" class="headerlink" title="桶排序"></a>桶排序</h2><p>桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。</p><h3 id="描述-8"><a href="#描述-8" class="headerlink" title="描述"></a>描述</h3><ul><li><p>设置一个定量的数组当作空桶；</p></li><li><p>遍历输入数据，并且把数据一个一个放到对应的桶里去；</p></li><li><p>对每个不是空的桶进行排序；</p></li><li><p>从不是空的桶里把排好序的数据拼接起来。</p><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//桶排序</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">bucketSort</span><span class="params">(<span class="type">int</span>[] arr)</span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (arr==<span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//最大值和最小值</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">max</span> <span class="operator">=</span> arr[<span class="number">0</span>];</span><br><span class="line">        <span class="type">int</span> <span class="variable">min</span> <span class="operator">=</span> arr[<span class="number">0</span>];</span><br><span class="line"></span><br><span class="line">        <span class="comment">//遍历数组 找出最大值和最小值</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (max&lt;arr[i])&#123;</span><br><span class="line">                max = arr[i];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (min&gt;arr[i])&#123;</span><br><span class="line">                min = arr[i];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//每个桶的容量（范围）</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">bucket</span> <span class="operator">=</span> (max - min) / arr.length + <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//桶的数量</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">nums</span> <span class="operator">=</span> (max - min ) / bucket + <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//记录索引</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//每一个桶是一个数组  所有桶的合计是一个数组</span></span><br><span class="line">        <span class="type">int</span>[][] bucketArr = <span class="keyword">new</span> <span class="title class_">int</span>[nums][arr.length-<span class="number">1</span>];</span><br><span class="line"></span><br><span class="line">        <span class="comment">//将元素组的所有数字根据不同范围放入不同的桶中</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; nums; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; arr.length; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (arr[j] &gt;= min + i * bucket &amp;&amp; arr[j] &lt; min + (i+<span class="number">1</span>) * bucket )&#123;</span><br><span class="line">                    bucketArr[i][index] = arr[j];</span><br><span class="line">                    index++;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            index = <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//在桶内使用希尔排序</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; bucketArr.length; i++) &#123;</span><br><span class="line">                <span class="keyword">new</span> <span class="title class_">InsertionSort</span>().shellSort(bucketArr[i]);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//重复利用记录索引</span></span><br><span class="line">        index = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//将桶内的所有元素放入原数组 （当元素为零是自动 排除 所以待排数组中 应 没有零 局限）</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; bucketArr.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; arr.length-<span class="number">1</span>; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (bucketArr[i][j]!=<span class="number">0</span>)&#123;</span><br><span class="line">                    arr[index] = bucketArr[i][j];</span><br><span class="line">                    index++;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure></li></ul><h2 id="基数排序"><a href="#基数排序" class="headerlink" title="基数排序"></a>基数排序</h2><p>基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。</p><h3 id="描述-9"><a href="#描述-9" class="headerlink" title="描述"></a>描述</h3><ul><li>取得数组中的最大数，并取得位数；</li><li>arr为原始数组，从最低位开始取每个位组成radix数组；</li><li>对radix进行计数排序（利用计数排序适用于小范围数的特点）；</li></ul><h1 id="树"><a href="#树" class="headerlink" title="树"></a>树</h1><h2 id="树和二叉树"><a href="#树和二叉树" class="headerlink" title="树和二叉树"></a>树和二叉树</h2><h3 id="树的概念"><a href="#树的概念" class="headerlink" title="树的概念"></a>树的概念</h3><p>树是一种数据结构，它是由<em>n(n≥0</em>)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：</p><ul><li>每个节点有零个或多个子节点；</li><li>没有父节点的节点称为根节点；</li><li>每一个非根节点有且只有一个父节点；</li><li>除了根节点外，每个子节点可以分为多个不相交的子树。</li></ul><h3 id="二叉树的概念"><a href="#二叉树的概念" class="headerlink" title="二叉树的概念"></a>二叉树的概念</h3><p>二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分</p><p>二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点</p><h3 id="满二叉树的概念"><a href="#满二叉树的概念" class="headerlink" title="满二叉树的概念"></a>满二叉树的概念</h3><p>除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。</p><p>国内定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1 ，则它就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，因为完全二叉树也满足这个要求，但不是满二叉树)</p><p>国外定义：a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.（如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。）</p><p>从数学上看，满二叉树的各个层的结点数形成一个首项为1，公比为2的等比数列。</p><p><strong>简单点说，满二叉树的每一个分支都是满的</strong></p><h3 id="完全二叉树的概念"><a href="#完全二叉树的概念" class="headerlink" title="完全二叉树的概念"></a>完全二叉树的概念</h3><p>一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。</p><p>一棵深度为k且有 2^k-1 个结点的二叉树称为满二叉树。</p><p>满二叉树每一层的结点个数都达到了最大值, 即满二叉树的第i层上有 2^i-1 个结点 (i≥1) 。</p><p>第i个节点的子节点（如果存在的话）为 2i+1 和 2i+2 父节点为 （i - 1）/ 2</p><p>如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。</p><p>从满二叉树和完全二叉树的定义可以看出, 满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树。</p><p><strong>简单点说，完全二叉树最后一个节点之前的所有节点都齐全</strong></p><h2 id="二分搜索树"><a href="#二分搜索树" class="headerlink" title="二分搜索树"></a>二分搜索树</h2><ul><li>二分搜索树的每个节点，都比左子树的节点值要大</li><li>二分搜索树的每个节点，都比右子树的节点值要小</li><li>二分搜索树是二叉树</li><li>每一棵子树也是二分搜索树</li></ul><p>泛化二分搜索树</p><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">BinarySearchTree</span>&lt;E <span class="keyword">extends</span> <span class="title class_">Comparable</span>&lt;E&gt;&gt; &#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">class</span> <span class="title class_">Node</span> &#123;</span><br><span class="line">        <span class="keyword">public</span> E e;</span><br><span class="line">        <span class="keyword">public</span> Node left;</span><br><span class="line">        <span class="keyword">public</span> Node right;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">public</span> <span class="title function_">Node</span><span class="params">(E e)</span>&#123;</span><br><span class="line">            <span class="built_in">this</span>.e = e;</span><br><span class="line">            <span class="built_in">this</span>.left=<span class="literal">null</span>;</span><br><span class="line">            <span class="built_in">this</span>.right=<span class="literal">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="meta">@Override</span></span><br><span class="line">        <span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span> &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="string">&quot;e=&quot;</span> + e;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> Node root;</span><br><span class="line">    <span class="keyword">private</span> <span class="type">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">BinarySearchTree</span><span class="params">()</span> &#123;</span><br><span class="line">        root = <span class="literal">null</span>;</span><br><span class="line">        size = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> Node <span class="title function_">getNode</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setNode</span><span class="params">(Node node)</span> &#123;</span><br><span class="line">        <span class="built_in">this</span>.root = node;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getSize</span><span class="params">()</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> size;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">isEmpty</span><span class="params">()</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size==<span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">add</span><span class="params">(E e)</span>&#123;</span><br><span class="line">        <span class="comment">//添加完e节点后 将root重置为树的根节点</span></span><br><span class="line">        root = add(root,e);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">    * 增加功能</span></span><br><span class="line"><span class="comment">    * node 根节点</span></span><br><span class="line"><span class="comment">    *  e 元素</span></span><br><span class="line"><span class="comment">    * */</span></span><br><span class="line">    <span class="keyword">private</span> Node <span class="title function_">add</span><span class="params">(Node node,E e)</span>&#123;</span><br><span class="line">        <span class="comment">//当node为null时表示已经是数的叶子节点 在这里创建新的叶子节点</span></span><br><span class="line">        <span class="keyword">if</span>(node == <span class="literal">null</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="title class_">Node</span>(e);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (e.compareTo(node.e) &lt; <span class="number">0</span>)&#123;</span><br><span class="line">            node.left = add(node.left,e);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (e.compareTo(node.e) &gt; <span class="number">0</span>)&#123;</span><br><span class="line">            node.right = add(node.right,e);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><p>三种遍历方式</p><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">* 前序遍历 中序遍历 后序遍历</span></span><br><span class="line"><span class="comment">*</span></span><br><span class="line"><span class="comment">* 前序遍历</span></span><br><span class="line"><span class="comment">* 当前节点 左子节点 右子节点</span></span><br><span class="line"><span class="comment">*</span></span><br><span class="line"><span class="comment">* 中序遍历</span></span><br><span class="line"><span class="comment">* 左子节点 当前节点 右子节点</span></span><br><span class="line"><span class="comment">*</span></span><br><span class="line"><span class="comment">* 后序遍历</span></span><br><span class="line"><span class="comment">* 左子节点 右子节点 当前节点</span></span><br><span class="line"><span class="comment">* */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">preOrder</span><span class="params">()</span>&#123;</span><br><span class="line">    preOrder(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">preOrder</span><span class="params">(Node node)</span>&#123;</span><br><span class="line">    <span class="comment">//终止条件</span></span><br><span class="line">    <span class="comment">//node左或右没有值是 就会为null 下面没有节点就不用遍历了</span></span><br><span class="line">    <span class="keyword">if</span> (node == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    System.out.print(node.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line"></span><br><span class="line">    preOrder(node.left);</span><br><span class="line">    preOrder(node.right);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">midOrder</span><span class="params">()</span>&#123;</span><br><span class="line">    midOrder(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">midOrder</span><span class="params">(Node node)</span>&#123;</span><br><span class="line">    <span class="comment">//终止条件</span></span><br><span class="line">    <span class="keyword">if</span> (node==<span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    midOrder(node.left);</span><br><span class="line"></span><br><span class="line">    System.out.print(node.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line"></span><br><span class="line">    midOrder(node.right);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">aftOrder</span><span class="params">()</span>&#123;</span><br><span class="line">    aftOrder(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">aftOrder</span><span class="params">(Node node)</span>&#123;</span><br><span class="line">    <span class="comment">//终止条件</span></span><br><span class="line">    <span class="keyword">if</span> (node==<span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    midOrder(node.left);</span><br><span class="line"></span><br><span class="line">    midOrder(node.right);</span><br><span class="line"></span><br><span class="line">    System.out.print(node.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>以上是深度优先遍历</p><p>下面的层序遍历是宽度优先遍历</p><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">levelOrderTraversal</span><span class="params">()</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">    <span class="comment">//层序遍历</span></span><br><span class="line">    levelOrderTraversal(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">levelOrderTraversal</span><span class="params">(Node node)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">    Queue&lt;Node&gt; queue = <span class="keyword">new</span> <span class="title class_">ArrayQueueDemo</span>&lt;&gt;();</span><br><span class="line"></span><br><span class="line">    queue.enqueue(node);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (!queue.isEmpty())&#123;</span><br><span class="line">        <span class="type">Node</span> <span class="variable">nodeF</span> <span class="operator">=</span> queue.dequeue();</span><br><span class="line">        System.out.print(nodeF.e+<span class="string">&quot; &quot;</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (nodeF.left!=<span class="literal">null</span>)&#123;</span><br><span class="line">            queue.enqueue(nodeF.left);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (nodeF.right!=<span class="literal">null</span>)&#123;</span><br><span class="line">            queue.enqueue(nodeF.right);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>查找最大值和最小值，仅需要遍历找出二叉搜索树的最右节点和最左节点即为最大值和最小值</p><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">findMax</span><span class="params">()</span> &#123;</span><br><span class="line">    <span class="comment">//查找最大值</span></span><br><span class="line">    findMax(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">findMax</span><span class="params">(Node node)</span> &#123;</span><br><span class="line">    <span class="keyword">while</span> (node.right!=<span class="literal">null</span>)&#123;</span><br><span class="line">        node = node.right;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    System.out.println(node.e);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">findMin</span><span class="params">()</span>&#123;</span><br><span class="line">    <span class="comment">//查找最小值</span></span><br><span class="line">    findMin(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">findMin</span><span class="params">(Node node)</span> &#123;</span><br><span class="line">    <span class="keyword">while</span> (node.left!=<span class="literal">null</span>)&#123;</span><br><span class="line">        node = node.left;</span><br><span class="line">    &#125;</span><br><span class="line">    System.out.println(node.e);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>删除</p><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> Node <span class="title function_">delete</span><span class="params">(Integer e)</span> <span class="keyword">throws</span> Exception &#123;</span><br><span class="line">    Node&lt;Integer&gt; currentNode = root;</span><br><span class="line">    Node&lt;Integer&gt; fatherNode = root;</span><br><span class="line"></span><br><span class="line">    <span class="type">boolean</span> <span class="variable">isLeft</span> <span class="operator">=</span> <span class="literal">false</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (!Objects.equals(e, currentNode.e)) &#123;</span><br><span class="line">        <span class="keyword">if</span> (e &lt; currentNode.e) &#123;</span><br><span class="line">            isLeft = <span class="literal">true</span>;</span><br><span class="line">            fatherNode = currentNode;</span><br><span class="line">            currentNode = currentNode.left;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            isLeft = <span class="literal">false</span>;</span><br><span class="line">            fatherNode = currentNode;</span><br><span class="line">            currentNode = currentNode.right;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (currentNode == <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="comment">//如果为空 则没有该元素的节点</span></span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">Exception</span>(<span class="string">&quot;未找到该元素&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (currentNode == root) &#123;</span><br><span class="line">        <span class="comment">//如果该节点为根 只需要将根重置即可</span></span><br><span class="line">        root = <span class="literal">null</span>;</span><br><span class="line">        <span class="keyword">return</span> currentNode;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (currentNode.left == <span class="literal">null</span> &amp;&amp; currentNode.right == <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="comment">//如果删除的节点是没有子节点的节点</span></span><br><span class="line">        <span class="keyword">if</span> (isLeft)&#123;</span><br><span class="line">            <span class="comment">//父节点的左子节点是要删除的节点</span></span><br><span class="line">            fatherNode.left=<span class="literal">null</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//父节点的右子节点是要删除的节点</span></span><br><span class="line">            fatherNode.right=<span class="literal">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (currentNode.left == <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="comment">//如果删除的节点是有一个子节点的节点</span></span><br><span class="line">        <span class="keyword">if</span> (isLeft)&#123;</span><br><span class="line">            fatherNode.left = currentNode.right;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            fatherNode.right = currentNode.right;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span>(currentNode.right == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span> (isLeft)&#123;</span><br><span class="line">            fatherNode.left = currentNode.left;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            fatherNode.right = currentNode.left;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="comment">//如果删除的节点是有两个子节点的节点</span></span><br><span class="line">        <span class="comment">//算了 不删了</span></span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> currentNode;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="平衡树"><a href="#平衡树" class="headerlink" title="平衡树"></a>平衡树</h2><p>如果向二叉树中插入9，8，7，6，5，4，3，2，1 后 如果查找1这个元素，查询速率会很低，效率低的原因在于这个数并不平衡，全部向左分支，如果我们有一种办法，能够不受插入数据的影响，让生成的树像完全二叉树那样，那么即使是在最坏的条件下，查找的效率依旧会很好</p><h3 id="2-3查找树"><a href="#2-3查找树" class="headerlink" title="2-3查找树"></a>2-3查找树</h3><p>为了保证查找树的平衡性，我们需要一些灵活性，因此在这里我们允许树中的一个结点保存多个键。确切的说，我们将一棵标准的二叉查找树中的结点称为2-结点(含有一个键和两条链)，而现在我们引入3-结点，它含有两个键和三条链。2结点和3-结点中的每条链都对应着其中保存的键所分割产生的一个区间。</p><h4 id="查找树的定义"><a href="#查找树的定义" class="headerlink" title="查找树的定义"></a>查找树的定义</h4><p>一颗2-3查找树要么为空，要么满足一下要求：</p><ul><li>2-结点<ul><li>含有一个键（及其对应的键）和两条链，左链接指向2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。</li></ul></li><li>3-结点<ul><li>含有两个键(及其对应的值)和三条链，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。</li></ul></li></ul><h4 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h4><p>将二叉查找树的查找算法一般化我们就能够直接得到2-3树的查找算法。要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中任意一个相等，查找命中;否则我们就根据比较的结果找到指向相应区间的连接，并在其指向的子树中递归地继续查找。如果这个是空链接，查找未命中。</p><h4 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h4><ul><li><p>向2-结点中插入新键</p><p>2-结点中只有一个key 那么将2-结点变成3-结点 在添加一个新key即可</p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913201424219.png" alt="image-20220913201424219"></p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913201442326.png" alt="image-20220913201442326"></p></li><li><p>向一棵只含有一个3-结点的树中插入新键</p><p>3-结点先临时变为4-结点（有三个key）将中间的key提升生成一个2-结点</p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913201837207.png" alt="image-20220913201837207"></p></li><li><p>向一个父节点为2-结点的3-结点中插入新值</p><p>将3-结点临时变为4-结点 将中间的值提升 添加到父节点 将父节点从2-结点变为3-结点（从一个key变为两个key）</p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913202014341.png" alt="image-20220913202014341"></p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913202037203.png" alt="image-20220913202037203"></p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913202044316.png" alt="image-20220913202044316"></p></li><li><p>向一个父节点为3-结点的3-结点插入新键</p><p>将3-结点变为临时4-结点 将中间键提出到父节点 父节点再变为临时4-结点 将中间键提出到他的父节点 其他两个变成两个2-结点</p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913202304771.png" alt="image-20220913202304771"></p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913202314769.png" alt="image-20220913202314769"></p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913202335206.png" alt="image-20220913202335206"></p></li><li><p>分解根节点</p><p>如果父节点是3-节点的根节点 将结点拆分为两个2-节点后 树的高度增加1</p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913202428311.png" alt="image-20220913202428311"></p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220913202443491.png" alt="image-20220913202443491"></p></li></ul><h4 id="2-3树性质"><a href="#2-3树性质" class="headerlink" title="2-3树性质"></a>2-3树性质</h4><p>通过对2-3树插入操作的分析，我们发现在插入的时候，2-3树需要做一些局部的变换来保持2-3树的平衡。一棵完全平衡的2-3树具有以下性质:</p><ol><li>任意空链接到根结点的路径长度都是相等的。</li><li>4-结点变换为3-结点时，树的高度不会发生变化，只有当根结点是临时的4-结点，分解根结点时，树高+1。</li><li>2-3树与普通二叉查找树最大的区别在于，普通的二叉查找树是自顶向下生长，而2-3树是自底向上生长。</li></ol><h3 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h3><p>​ 树可能会不平衡如果存入数据为以下：8，9，10，11，14，16，17 时 存入的树就像链表一样，是一维的并不是二维的，这时时间复杂度就从树的O(logN)变成O(N)</p><p>红黑树主要是对2-3树进行编码，红黑树背后的基本思想是用标准的二叉查找树（完全由2-结点构成）和一些额外信息（替换3-结点）来表示2-3树。树的链接分为两种类型：</p><p><strong>红链接</strong>：将两个2-结点连接起来构成一个3-结点</p><p><strong>黑链接</strong>：则是2-3树中的普通链接</p><h4 id="红黑树的特征"><a href="#红黑树的特征" class="headerlink" title="红黑树的特征"></a>红黑树的特征</h4><p>有两个特征，一个简单，另一个比较复杂：</p><ul><li>节点都有颜色</li><li>在插入和删除的过程中，要遵循保持这些颜色的不同排列的规则</li></ul><h4 id="红-黑规则"><a href="#红-黑规则" class="headerlink" title="红-黑规则"></a>红-黑规则</h4><p>​ 当插入（或者删除）一个新节点时，必须要遵循一定的规则，它们被称为红-黑规则。如果遵循这些规则，树就是平衡的。</p><ol><li>每一个节点不是红色就是黑色的</li><li>根总是黑色的</li><li>如果节点是红色的，则它的节点必须是黑色的（反之倒不一定必须为真）</li><li>从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点</li><li>红链接总为左链接</li></ol><p>在从根到叶节点的路径上的黑色节点的数目称为黑色高度( black height)。规则4的另一种陈述方法是所有从根到叶节点路径上的黑色高度必须相同。</p><h4 id="红黑树节点设计"><a href="#红黑树节点设计" class="headerlink" title="红黑树节点设计"></a>红黑树节点设计</h4><p>左子节点 右子节点 key值 value值 颜色（是否为红链接）</p><h4 id="红黑树对平衡的补救"><a href="#红黑树对平衡的补救" class="headerlink" title="红黑树对平衡的补救"></a>红黑树对平衡的补救</h4><p>​ 为了能以较快的时间O(logN)来搜索一棵树，需要保证树总是平衡的（或者至少大部分是平衡的)。这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。<br>​ 红-黑树的平衡是在插入的过程中（删除时也是，但暂时忽略这个问题）取得的。对一个要插入的数据项，插入例程要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。</p><p>左旋</p><p>当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋</p><p>左旋过程：</p><ol><li>让x的左子结点变为h的右子结点：<code>h.right=x.left</code></li><li>让h成为x的左子结点：<code>x.left=h;</code></li><li>让h的color属性变为x的color属性值：<code>x.color=h.color;</code></li><li>让h的color属性变为RED：<code>h.color=true;</code></li></ol><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220916154507982.png" alt="image-20220916154507982"></p><p>右旋</p><p>当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋</p><p>右旋过程：</p><ol><li>让x的右子结点成为h的左子结点:<code>h.left = x.right;</code></li><li>让h成为x的右子结点:<code>x.right=h;</code></li><li>让x的color变为h的color属性值:<code>x.color = h.color;</code></li><li>让h的color为RED</li></ol><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220916155136635.png" alt="image-20220916155136635"></p><p>然后进行颜色反转</p><h4 id="插入-1"><a href="#插入-1" class="headerlink" title="插入"></a>插入</h4><p>向2-结点插入</p><ul><li>如果新建结点小于当前 只需新增一个红色结点</li><li>如果新建结点大于当前 先插入一个红色结点后在进行左旋</li></ul><h4 id="颜色反转"><a href="#颜色反转" class="headerlink" title="颜色反转"></a>颜色反转</h4><p>当一个结点的左子结点和右子结点的color都为RED时，也就是出现了临时的4-结点，此时只需要把左子结点和右子结点的颜色变为BLACK，同时让当前结点的颜色变为RED即可。</p><p><img src="/../imags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/image-20220916162217689.png" alt="image-20220916162217689"></p><h4 id="API设计"><a href="#API设计" class="headerlink" title="API设计"></a>API设计</h4><table><thead><tr><th>类名</th><th><code>RedBlackTree&lt;Key extends comparable&lt;Key&gt;, value&gt;</code></th></tr></thead><tbody><tr><td>构造方法</td><td><code>RedBlackTree():创建RedBlackTree对象</code></td></tr><tr><td>成员方法</td><td>1.<code>private boolean isRed(Node x)</code>:判断当前结点的父指向链接是否为红色<br>2.<code>private Node rotateLeft(Node h)</code>:左旋调整<br>3.<code>private Node rotateRight(Node h)</code>:右旋调整<br>4.<code>private void flipColors(Node h)</code>:颜色反转,相当于完成拆分4-结点<br>5.<code>public void put(Key key, Value val)</code>:在整个树上完成插入操作<br>6.<code>private Node put(Node h, Key key, value val)</code>:在指定树中，完成插入操作,并返回添加元素后新的树<br>7.<code>public value get(Key key)</code>:根据key，从树中找出对应的值<br>8.<code>private Value get(Node x, Key key)</code>:从指定的树x中，找出key对应的值<br>9.<code>public int size()</code>:获取树中元素的个数</td></tr><tr><td>成员变量</td><td>1.<code>private Node root</code>:记录根结点<br>2.<code>private int N</code>:记录树中元素的个数<br>3.<code>private static boolean RED</code>:红色链接标识<br>4.<code>private static boolean BLACK</code>:黑色链接标识</td></tr></tbody></table><h2 id="B树"><a href="#B树" class="headerlink" title="B树"></a>B树</h2><p>在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。</p><h3 id="B树的特性"><a href="#B树的特性" class="headerlink" title="B树的特性"></a>B树的特性</h3><p>B数中允许一个结点包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在我们选择一个参数M,来<br>构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点︰</p><ul><li>每个结点最多有M-1个key ，并且以并序排列;</li><li>每个结点最多能有M个子结点;</li><li>根结点至少有两个子结点;</li></ul><h3 id="B树存储数据"><a href="#B树存储数据" class="headerlink" title="B树存储数据"></a>B树存储数据</h3><h3 id="B数应用"><a href="#B数应用" class="headerlink" title="B数应用"></a>B数应用</h3><p>磁盘存储</p><h2 id="B-树"><a href="#B-树" class="headerlink" title="B+树"></a>B+树</h2><p>B+树是对B树的一种变形树，它与B树的差异在于:</p><ol><li>非叶结点仅具有索引作用，也就是说，非叶子结点只存储key，不存储value</li><li>树的所有叶结点构成一个有序链表，可以按照key排序的次序遍历全部数据。</li></ol><h3 id="B-树存储数据"><a href="#B-树存储数据" class="headerlink" title="B+树存储数据"></a>B+树存储数据</h3><h3 id="B-树和B树的对比"><a href="#B-树和B树的对比" class="headerlink" title="B+树和B树的对比"></a>B+树和B树的对比</h3><p>B+树的优点在于∶</p><ol><li><p>由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key。</p></li><li><p>B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。</p></li></ol><p>B树的优点在于:<br>由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到Kkey所在的位置，就能找到value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶子结点的深度，才能找到value。</p><h3 id="B-树的应用"><a href="#B-树的应用" class="headerlink" title="B+树的应用"></a>B+树的应用</h3><p>数据库存储</p><h1 id="堆"><a href="#堆" class="headerlink" title="堆"></a>堆</h1><p>堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树(逻辑层面上)的数组对象(物理层面上),常用来在一组变化频繁(发生增删查改的频率较高)的数据中寻找最值.将根结点最大的堆叫做最大堆或大根堆，这样可以找到堆中的最大值(根节点的值);根结点最小的堆叫做最小堆或小根堆,这样可以找到堆中的最小值。</p><p>堆是有如下特点的二叉树</p><ul><li>它是完全二叉树。</li><li>它常常用一个数组实现</li><li>堆中的每一个节点都满足堆的条件，每一个节点的关键字都大于（或等于）这个节点的子节点的关键字</li></ul><h3 id="堆的向下调整"><a href="#堆的向下调整" class="headerlink" title="堆的向下调整"></a>堆的向下调整</h3><p>(以小堆为例）</p><ol><li>先设定根节点为当前节点(通过下标获取，标记为cur)，比较左右子树的值，找出更小的值，用child来标记。</li><li>比较child和cur的值，如果child比cur小，则不满足小堆的规则，需要进行交换。</li><li>如果child比cur大，满足小堆的规则，不需要交换，调整结束。</li><li>处理完一个节点之后，从当前的child出发，循环之前的过程。</li></ol><p>下面我们给出两个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。</p><p>根节点左右子树不是堆，我们怎么调整呢？</p><p>这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。</p><h3 id="堆的向上调整"><a href="#堆的向上调整" class="headerlink" title="堆的向上调整"></a>堆的向上调整</h3><p>(以小堆为例）</p><ol><li>先设定倒数的第一个叶子节点为当前节点(通过下标获取，标记为cur)，找出他的父亲节点，用parent来标记。</li><li>比较parent和cur的值，如果cur比parent小，则不满足小堆的规则，需要进行交换。</li><li>如果cur比parent大，满足小堆的规则，不需要交换，调整结束。</li><li>处理完一个节点之后，从当前的parent出发，循环之前的过程。</li></ol><h3 id="堆的插入"><a href="#堆的插入" class="headerlink" title="堆的插入"></a>堆的插入</h3><p>将数据插入到数组最后，再进行向上调整。</p><h3 id="堆的删除"><a href="#堆的删除" class="headerlink" title="堆的删除"></a>堆的删除</h3><p>删除堆是删除堆顶的数据。</p><p>将堆顶的数据和最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。</p><h1 id="图"><a href="#图" class="headerlink" title="图"></a>图</h1><h2 id="定义"><a href="#定义" class="headerlink" title="定义"></a>定义</h2><p>图是由<strong>顶点</strong>（vertice）集和<strong>边</strong>（edge）集组成的，图又分为<strong>有向图</strong>、<strong>无向图</strong>、<strong>带权图</strong></p><p>有向图：顾名思义就是具有方向的图，如上所示，顶点1指向顶点2，但是顶点2无法指向顶点1。</p><p>无向图：就是不区分方向的图，顶点1可以指向顶点2,同时顶点2也可以指向顶点1。</p><p>带权图：表示边带有权重的图</p><h3 id="邻接"><a href="#邻接" class="headerlink" title="邻接"></a>邻接</h3><p>如果两个顶点被同一条边连接，就称这两个顶点是邻接的。</p><h3 id="路径"><a href="#路径" class="headerlink" title="路径"></a>路径</h3><p>路径是边的序列。</p><h3 id="连通图"><a href="#连通图" class="headerlink" title="连通图"></a>连通图</h3><p>如果至少有一条路径可以连接起所有的顶点，那么这个图被称作连通的</p><h3 id="权和网"><a href="#权和网" class="headerlink" title="权和网"></a>权和网</h3><p>每条边可以标上某种含义的数值，该数值称为边上的权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。</p><h3 id="度"><a href="#度" class="headerlink" title="度"></a>度</h3><p>某个顶点的度就是依赖于该顶点的边的个数</p><h3 id="环"><a href="#环" class="headerlink" title="环"></a>环</h3><p>是一条至少含有一条边且终点和起点相同的路径</p><h2 id="图的存储结构"><a href="#图的存储结构" class="headerlink" title="图的存储结构"></a>图的存储结构</h2><h3 id="邻接矩阵"><a href="#邻接矩阵" class="headerlink" title="邻接矩阵"></a>邻接矩阵</h3><h3 id="邻接表"><a href="#邻接表" class="headerlink" title="邻接表"></a>邻接表</h3></article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者:</span> <span class="post-copyright-info"><a href="https://mengfanmingx.gitee.io/">寒兔丶</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接:</span> <span class="post-copyright-info"><a href="https://mengfanmingx.gitee.io/posts/2022/12/24/data%20structure&amp;algorithm/">https://mengfanmingx.gitee.io/posts/2022/12/24/data%20structure&amp;algorithm/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明:</span> <span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://mengfanmingx.gitee.io" target="_blank">麻辣兔头川菜馆</a>！</span></div></div><div class="tag_share"><div class="post_share"><div class="social-share" data-image="/img/default_cover1.png" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/css/share.min.css" media="print" onload='this.media="all"'><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/posts/2022/09/28/MySQL/"><img class="prev-cover" src="/img/default_cover.png" onerror='onerror=null,src="/img/404.jpg"' alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">mysql</div></div></a></div><div class="next-post pull-right"><a href="/posts/2023/03/16/class/"><img class="next-cover" src="/img/default_cover1.png" onerror='onerror=null,src="/img/404.jpg"' alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">java常用类</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/posts/2022/09/28/MySQL/" title="mysql"><img class="cover" src="/img/default_cover.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-09-28</div><div class="title">mysql</div></div></a></div><div><a href="/posts/2022/08/24/Linux/" title="Linux学习笔记"><img class="cover" src="/img/default_cover1.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-08-24</div><div class="title">Linux学习笔记</div></div></a></div><div><a href="/posts/2023/03/16/class/" title="java常用类"><img class="cover" src="/img/default_cover1.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-03-16</div><div class="title">java常用类</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%B8%B8%E7%94%A8%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-number">1.</span> <span class="toc-text">常用数据结构</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%9B%9B%E7%A7%8D%E5%AD%98%E5%82%A8%E6%96%B9%E5%BC%8F"><span class="toc-number">2.</span> <span class="toc-text">四种存储方式</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8"><span class="toc-number">2.1.</span> <span class="toc-text">顺序存储</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%93%BE%E6%8E%A5%E5%AD%98%E5%82%A8"><span class="toc-number">2.2.</span> <span class="toc-text">链接存储</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%B4%A2%E5%BC%95%E5%AD%98%E5%82%A8"><span class="toc-number">2.3.</span> <span class="toc-text">索引存储</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%A3%E5%88%97%E5%AD%98%E5%82%A8"><span class="toc-number">2.4.</span> <span class="toc-text">散列存储</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%BA%BF%E6%80%A7%E7%BB%93%E6%9E%84%E5%92%8C%E9%9D%9E%E7%BA%BF%E6%80%A7%E7%BB%93%E6%9E%84"><span class="toc-number">3.</span> <span class="toc-text">线性结构和非线性结构</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%BA%BF%E6%80%A7%E7%BB%93%E6%9E%84"><span class="toc-number">3.1.</span> <span class="toc-text">线性结构</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%9D%9E%E7%BA%BF%E6%80%A7%E7%BB%93%E6%9E%84"><span class="toc-number">3.2.</span> <span class="toc-text">非线性结构</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84"><span class="toc-number">4.</span> <span class="toc-text">稀疏数组</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%80%E4%BB%8B"><span class="toc-number">4.1.</span> <span class="toc-text">简介</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BA%94%E7%94%A8%E5%AE%9E%E4%BE%8B"><span class="toc-number">4.2.</span> <span class="toc-text">应用实例</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="toc-number">4.3.</span> <span class="toc-text">代码实现</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E7%BB%84"><span class="toc-number">5.</span> <span class="toc-text">数组</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8"><span class="toc-number">6.</span> <span class="toc-text">链表</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%A0%88"><span class="toc-number">7.</span> <span class="toc-text">栈</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BA%95%E5%B1%82%E6%95%B0%E7%BB%84"><span class="toc-number">7.1.</span> <span class="toc-text">底层数组</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BA%95%E5%B1%82%E9%93%BE%E8%A1%A8"><span class="toc-number">7.2.</span> <span class="toc-text">底层链表</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E9%98%9F%E5%88%97"><span class="toc-number">8.</span> <span class="toc-text">队列</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BA%95%E5%B1%82%E6%95%B0%E7%BB%84-1"><span class="toc-number">8.1.</span> <span class="toc-text">底层数组</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BA%95%E5%B1%82%E9%93%BE%E8%A1%A8-1"><span class="toc-number">8.2.</span> <span class="toc-text">底层链表</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%89%A9%E5%85%85%EF%BC%9A%E5%8F%8C%E5%90%91%E9%98%9F%E5%88%97"><span class="toc-number">8.3.</span> <span class="toc-text">扩充：双向队列</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%8E%92%E5%BA%8F"><span class="toc-number">9.</span> <span class="toc-text">排序</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%8B%E7%BB%8D"><span class="toc-number">9.1.</span> <span class="toc-text">介绍</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%88%86%E7%B1%BB%E5%92%8C%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">9.2.</span> <span class="toc-text">分类和算法复杂度</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F"><span class="toc-number">9.3.</span> <span class="toc-text">冒泡排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0"><span class="toc-number">9.3.1.</span> <span class="toc-text">描述</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F"><span class="toc-number">9.4.</span> <span class="toc-text">快速排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0-1"><span class="toc-number">9.4.1.</span> <span class="toc-text">描述</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%80%E5%8D%95%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F"><span class="toc-number">9.5.</span> <span class="toc-text">简单插入排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0-2"><span class="toc-number">9.5.1.</span> <span class="toc-text">描述</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F"><span class="toc-number">9.6.</span> <span class="toc-text">希尔排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0-3"><span class="toc-number">9.6.1.</span> <span class="toc-text">描述</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F"><span class="toc-number">9.7.</span> <span class="toc-text">选择排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0-4"><span class="toc-number">9.7.1.</span> <span class="toc-text">描述</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A0%86%E6%8E%92%E5%BA%8F"><span class="toc-number">9.8.</span> <span class="toc-text">堆排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0-5"><span class="toc-number">9.8.1.</span> <span class="toc-text">描述</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F"><span class="toc-number">9.9.</span> <span class="toc-text">归并排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0-6"><span class="toc-number">9.9.1.</span> <span class="toc-text">描述</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F"><span class="toc-number">9.10.</span> <span class="toc-text">计数排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0-7"><span class="toc-number">9.10.1.</span> <span class="toc-text">描述</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A1%B6%E6%8E%92%E5%BA%8F"><span class="toc-number">9.11.</span> <span class="toc-text">桶排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0-8"><span class="toc-number">9.11.1.</span> <span class="toc-text">描述</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F"><span class="toc-number">9.12.</span> <span class="toc-text">基数排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%8F%E8%BF%B0-9"><span class="toc-number">9.12.1.</span> <span class="toc-text">描述</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%A0%91"><span class="toc-number">10.</span> <span class="toc-text">树</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A0%91%E5%92%8C%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">10.1.</span> <span class="toc-text">树和二叉树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A0%91%E7%9A%84%E6%A6%82%E5%BF%B5"><span class="toc-number">10.1.1.</span> <span class="toc-text">树的概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%A6%82%E5%BF%B5"><span class="toc-number">10.1.2.</span> <span class="toc-text">二叉树的概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%BB%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%A6%82%E5%BF%B5"><span class="toc-number">10.1.3.</span> <span class="toc-text">满二叉树的概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%A6%82%E5%BF%B5"><span class="toc-number">10.1.4.</span> <span class="toc-text">完全二叉树的概念</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E6%A0%91"><span class="toc-number">10.2.</span> <span class="toc-text">二分搜索树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%B9%B3%E8%A1%A1%E6%A0%91"><span class="toc-number">10.3.</span> <span class="toc-text">平衡树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3%E6%9F%A5%E6%89%BE%E6%A0%91"><span class="toc-number">10.3.1.</span> <span class="toc-text">2-3查找树</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%9F%A5%E6%89%BE%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89"><span class="toc-number">10.3.1.1.</span> <span class="toc-text">查找树的定义</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%9F%A5%E6%89%BE"><span class="toc-number">10.3.1.2.</span> <span class="toc-text">查找</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8F%92%E5%85%A5"><span class="toc-number">10.3.1.3.</span> <span class="toc-text">插入</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-3%E6%A0%91%E6%80%A7%E8%B4%A8"><span class="toc-number">10.3.1.4.</span> <span class="toc-text">2-3树性质</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91"><span class="toc-number">10.3.2.</span> <span class="toc-text">红黑树</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E7%89%B9%E5%BE%81"><span class="toc-number">10.3.2.1.</span> <span class="toc-text">红黑树的特征</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%BA%A2-%E9%BB%91%E8%A7%84%E5%88%99"><span class="toc-number">10.3.2.2.</span> <span class="toc-text">红-黑规则</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91%E8%8A%82%E7%82%B9%E8%AE%BE%E8%AE%A1"><span class="toc-number">10.3.2.3.</span> <span class="toc-text">红黑树节点设计</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91%E5%AF%B9%E5%B9%B3%E8%A1%A1%E7%9A%84%E8%A1%A5%E6%95%91"><span class="toc-number">10.3.2.4.</span> <span class="toc-text">红黑树对平衡的补救</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8F%92%E5%85%A5-1"><span class="toc-number">10.3.2.5.</span> <span class="toc-text">插入</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E9%A2%9C%E8%89%B2%E5%8F%8D%E8%BD%AC"><span class="toc-number">10.3.2.6.</span> <span class="toc-text">颜色反转</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#API%E8%AE%BE%E8%AE%A1"><span class="toc-number">10.3.2.7.</span> <span class="toc-text">API设计</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#B%E6%A0%91"><span class="toc-number">10.4.</span> <span class="toc-text">B树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#B%E6%A0%91%E7%9A%84%E7%89%B9%E6%80%A7"><span class="toc-number">10.4.1.</span> <span class="toc-text">B树的特性</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#B%E6%A0%91%E5%AD%98%E5%82%A8%E6%95%B0%E6%8D%AE"><span class="toc-number">10.4.2.</span> <span class="toc-text">B树存储数据</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#B%E6%95%B0%E5%BA%94%E7%94%A8"><span class="toc-number">10.4.3.</span> <span class="toc-text">B数应用</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#B-%E6%A0%91"><span class="toc-number">10.5.</span> <span class="toc-text">B+树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#B-%E6%A0%91%E5%AD%98%E5%82%A8%E6%95%B0%E6%8D%AE"><span class="toc-number">10.5.1.</span> <span class="toc-text">B+树存储数据</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#B-%E6%A0%91%E5%92%8CB%E6%A0%91%E7%9A%84%E5%AF%B9%E6%AF%94"><span class="toc-number">10.5.2.</span> <span class="toc-text">B+树和B树的对比</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#B-%E6%A0%91%E7%9A%84%E5%BA%94%E7%94%A8"><span class="toc-number">10.5.3.</span> <span class="toc-text">B+树的应用</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%A0%86"><span class="toc-number">11.</span> <span class="toc-text">堆</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%A0%86%E7%9A%84%E5%90%91%E4%B8%8B%E8%B0%83%E6%95%B4"><span class="toc-number">11.0.1.</span> <span class="toc-text">堆的向下调整</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%A0%86%E7%9A%84%E5%90%91%E4%B8%8A%E8%B0%83%E6%95%B4"><span class="toc-number">11.0.2.</span> <span class="toc-text">堆的向上调整</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%A0%86%E7%9A%84%E6%8F%92%E5%85%A5"><span class="toc-number">11.0.3.</span> <span class="toc-text">堆的插入</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%A0%86%E7%9A%84%E5%88%A0%E9%99%A4"><span class="toc-number">11.0.4.</span> <span class="toc-text">堆的删除</span></a></li></ol></li></ol><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%9B%BE"><span class="toc-number">12.</span> <span class="toc-text">图</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%9A%E4%B9%89"><span class="toc-number">12.1.</span> <span class="toc-text">定义</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%82%BB%E6%8E%A5"><span class="toc-number">12.1.1.</span> <span class="toc-text">邻接</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%B7%AF%E5%BE%84"><span class="toc-number">12.1.2.</span> <span class="toc-text">路径</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BF%9E%E9%80%9A%E5%9B%BE"><span class="toc-number">12.1.3.</span> <span class="toc-text">连通图</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9D%83%E5%92%8C%E7%BD%91"><span class="toc-number">12.1.4.</span> <span class="toc-text">权和网</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BA%A6"><span class="toc-number">12.1.5.</span> <span class="toc-text">度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%8E%AF"><span class="toc-number">12.1.6.</span> <span class="toc-text">环</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9B%BE%E7%9A%84%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84"><span class="toc-number">12.2.</span> <span class="toc-text">图的存储结构</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5"><span class="toc-number">12.2.1.</span> <span class="toc-text">邻接矩阵</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%82%BB%E6%8E%A5%E8%A1%A8"><span class="toc-number">12.2.2.</span> <span class="toc-text">邻接表</span></a></li></ol></li></ol></li></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2022 - 2023 By 寒兔丶</div><div class="framework-info"><span>框架</span> <a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题</span> <a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text">别看了，什么都没有了！QwQ</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i><span id="percent">0</span></button></div></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i> <span>数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"></div></div><hr><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div><script src="https://unpkg.com/hexo-theme-butterfly/source/js/utils.js"></script><script src="https://unpkg.com/hexo-theme-butterfly/source/js/main.js"></script><script src="https://unpkg.com/hexo-theme-butterfly/source/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.umd.min.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script src="https://unpkg.com/hexo-theme-butterfly/source/js/search/local-search.js"></script><script>var preloader={endLoading:()=>{document.body.style.overflow="auto",document.getElementById("loading-box").classList.add("loaded")},initLoading:()=>{document.body.style.overflow="",document.getElementById("loading-box").classList.remove("loaded")}};window.addEventListener("load",preloader.endLoading())</script><div class="js-pjax"></div><div class="aplayer no-destroy" data-id="7322622901" data-server="tencent" data-type="playlist" data-fixed="true" data-mini="true" data-listfolded="false" data-order="random" data-preload="auto" data-volume="0.4" data-lrctype="-1"></div><script>window.onload=function(){document.getElementsByTagName("html")[0].setAttribute("data-theme","light")}</script><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css" media="print" onload='this.media="all"'><script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/metingjs/dist/Meting.min.js"></script><script src="https://cdn.jsdelivr.net/npm/pjax/pjax.js"></script><script>let pjaxSelectors=["head > title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show",".js-pjax"];var pjax=new Pjax({elements:'a:not([target="_blank"])',selectors:pjaxSelectors,cacheBust:!1,analytics:!1,scrollRestoration:!1});document.addEventListener("pjax:send",(function(){if(window.tocScrollFn&&window.removeEventListener("scroll",window.tocScrollFn),window.scrollCollect&&window.removeEventListener("scroll",scrollCollect),"object"==typeof preloader&&preloader.initLoading(),document.getElementById("rightside").style.cssText="opacity: ''; transform: ''",window.aplayers)for(let e=0;e<window.aplayers.length;e++)window.aplayers[e].options.fixed||window.aplayers[e].destroy();"object"==typeof typed&&typed.destroy();const e=document.body.classList;e.contains("read-mode")&&e.remove("read-mode"),"object"==typeof disqusjs&&disqusjs.destroy()})),document.addEventListener("pjax:complete",(function(){window.refreshFn(),document.querySelectorAll("script[data-pjax]").forEach((e=>{const t=document.createElement("script"),o=e.text||e.textContent||e.innerHTML||"";Array.from(e.attributes).forEach((e=>t.setAttribute(e.name,e.value))),t.appendChild(document.createTextNode(o)),e.parentNode.replaceChild(t,e)})),GLOBAL_CONFIG.islazyload&&window.lazyLoadInstance.update(),"function"==typeof chatBtnFn&&chatBtnFn(),"function"==typeof panguInit&&panguInit(),"function"==typeof gtag&&gtag("config","",{page_path:window.location.pathname}),"object"==typeof _hmt&&_hmt.push(["_trackPageview",window.location.pathname]),"function"==typeof loadMeting&&document.getElementsByClassName("aplayer").length&&loadMeting(),"object"==typeof Prism&&Prism.highlightAll(),"object"==typeof preloader&&preloader.endLoading()})),document.addEventListener("pjax:error",(e=>{404===e.request.status&&pjax.loadUrl("/404.html")}))</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div><script data-pjax>function butterfly_clock_injector_config(){var c=document.getElementsByClassName("sticky_layout")[0];console.log("已挂载butterfly_clock"),c.insertAdjacentHTML("afterbegin",'<div class="card-widget card-clock"><div class="card-glass"><div class="card-background"><div class="card-content"><div id="hexo_electric_clock"><img class="entered loading" id="card-clock-loading" src="https://npm.elemecdn.com/hexo-butterfly-clock/lib/loading.gif" style="height: 120px; width: 100%;" data-ll-status="loading"/></div></div></div></div></div>')}for(var elist="/posts/".split(","),cpage=location.pathname,epage="all",flag=0,i=0;i<elist.length;i++)cpage.includes(elist[i])&&flag++;("all"===epage&&0==flag||epage===cpage)&&butterfly_clock_injector_config()</script><script src="https://pv.sohu.com/cityjson?ie=utf-8"></script><script data-pjax src="https://npm.elemecdn.com/hexo-butterfly-clock/lib/clock.min.js"></script></body></html><div id="sakana-widget" style="position:fixed;bottom:10px;right:10px"></div><script>function initSakanaWidget(){(new SakanaWidget).mount("#sakana-widget")}</script><script async onload="initSakanaWidget()" src="https://cdn.jsdelivr.net/npm/sakana-widget@2.2.1/lib/sakana.min.js"></script>